勉強 @ 最大長方形の面積 Largest Rectangle

Code Jam Africa 2011の予選C問題
に、縦方向にヒストグラム化してから最大長方形面積決定プログラム
で挑戦。

考え方としては
1.各マスから特定方向への連続可能数を決定。
2.ヒストグラムを横にみていく

目からうろこな方法。

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <cassert>
#include <ctime>

#define DEBUG_MODE (0)

using namespace std;

void debug_print(vector<int> &map, int width, int height)
{
#if DEBUG_MODE
	for(int h=0; h<height; ++h)
	{
		for(int w=0; w<width; ++w)
		{
			cout << map[h*width+w];
		}
		cout << endl;
	}
	cout << endl;
#endif
}

struct Rect
{
	int start;
	int height;
};

int get_largest_rectangle_in_histgram(const vector<int> &histgram)
{
	int max_area = 0;
	stack<Rect> rects;

	for(int i=0; i<histgram.size(); ++i)
	{
		int height = histgram[i];

		if (rects.empty())
		{
			Rect r;
			r.start = i;
			r.height = height;
			rects.push(r);
		}
		else
		{
			int restart = i;
			while(!rects.empty() && rects.top().height >= height)
			{
				Rect pre = rects.top();
				rects.pop();

				restart = pre.start;
				int width = (i - restart);
				int area = pre.height * width;
				max_area = max(area, max_area);
			}

			Rect r;
			r.start = restart;
			r.height = height;
			rects.push(r);
		}
	}

	while(!rects.empty())
	{
		Rect pre = rects.top();
		rects.pop();

		int width = (histgram.size() - pre.start);
		int area = pre.height * width;
		max_area = max(area, max_area);
	}

	return max_area;
}

vector<int> make_histgram_from_map(const vector<int> &map, int width, int height)
{
	vector<int> histgram(height*width);

	for(int h=0; h<height; ++h)
	{
		for(int w=0; w<width; ++w)
		{
			if (0==h)
			{
				histgram[h*width+w] = map[w];
			}
			else
			{
				int index = h*width+w;
				int index_up = index-width;

				histgram[h*width+w] = map[index] ? histgram[index_up]+1 : 0;
			}
		}
	}

	return histgram;
}

int get_max_rectangle_in_map(const vector<int> &map, int width, int height)
{
	vector<int> histgram = make_histgram_from_map(map, width, height);

	debug_print(histgram, width, height);

	int max_area = 0;
	for(int h=0; h<height; ++h)
	{
		vector<int> line(width);
		for(int w=0; w<width; ++w)
		{
			line[w] = histgram[h*width+w];
		}

		max_area = max(max_area, get_largest_rectangle_in_histgram(line));
	}

	return max_area;
}

void input_a_case(ifstream &in, vector<int> &map, int &width, int &height)
{
	in >> width;
	in >> height;

	for(int h=0; h<height; ++h)
	{
		for(int w=0; w<width; ++w)
		{
			char c;
			in >> c;

			bool ok = 'G'==c || 'S'==c;

			map.push_back(ok ? 1 : 0);
		}
	}
}

void solve_a_case(ifstream &in, int &area)
{
	vector<int> map;
	int width = 0;
	int height = 0;

	input_a_case(in, map, width, height);

	area = get_max_rectangle_in_map(map, width, height);
}

void solve_all_cases(ifstream &in, ofstream &out)
{
	int case_num = 0;

	in >> case_num;
	for(int i=0; i<case_num; i++)
	{
		int area = 0;

		solve_a_case(in, area);

		out << "Case #" << i+1 << ": ";
		out << area << endl;
	}
}

int main()
{
#if 0
	ifstream in("in.txt");
	ofstream out("out.txt");
#elif 0
	ifstream in("C-small-practice.in");
	ofstream out("C-small-practice.out");
#elif 1
	ifstream in("C-large-practice.in");
	ofstream out("C-large-practice.out");
#endif

	solve_all_cases(in, out);

	return 0;
}

さすがに速い。
一列の終わりに高さ０の番兵仕込めば、もちっとスッキリするかな。
上方向に連結数を見てるから、下の列から面積決定して、暫定最大面積で枝狩りするのもいいかもしれない。
ただ、連結条件が上下左右に関連すると対応できない気がする。
柔軟性は力ずくが上か。。