Разбор задания с олимпиады

[neomax38]

Международная олимпиада АСМ по программированию
(четвертьфинал) 2009
Задача B
Прямоугольники
Входные данные читать из файла BOXES.IN в текущем каталоге. Выходные данные выводить в стандартный поток данных (на дисплей). Исходный текст программы направлять на решение в файле BOXES.CPP или BOXES.DPR
Ограничение по времени 10 секунд
Ограничение по памяти 64 Мбайта

На плоскости расположено несколько прямоугольников. Каждый прямоугольник на плоскости задается координатами левого нижнего угла (X1, Y1) и правого верхнего угла (X2, Y2), при этом стороны прямоугольников параллельны осям координат. При наложении друг на друга прямоугольники образуют фигуры, отдельно расположенный прямоугольник - тоже фигура. Прямоугольники, соприкасающиеся только углами, не образуют фигуру. Если прямоугольники соприкасаются сторонами, то они тоже образуют фигуру. Требуется определить фигуру максимальной площади (в качестве ответа вывести площадь такой фигуры).
Входные данные:
В первой строке входного файла содержится количество тестов. В первой строке каждого теста записано количество прямоугольников N, далее идут N строк с координатами вершин прямоугольников X1 Y1 X2 Y2. Координаты вершин - целые, неотрицательные числа, в диапазоне от 0 до 100 включительно. Количество прямоугольников не больше 25.

Сам в С++ не разбираюсь. Нужно сам алгоритм понять.

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <queue>
#include <cassert>

using namespace std;

vector<vector<int> > field;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void assert_coord(int c)
{
	assert(c >= 0 && c <= 100);
}

void bfs(int x, int y, int h)
{
	queue<int> qx;
	queue<int> qy;

	field[x][y] = h;
	qx.push(x);
	qy.push(y);

	while (!qx.empty())
	{
		int vx, vy;
		vx = qx.front();
		vy = qy.front();
		qx.pop();
		qy.pop();

		for (int i = 0;i < 4;i++)
		{
			int nx = vx + dx[i];
			int ny = vy + dy[i];
			if (nx >= 0 && ny >= 0 && field[nx][ny] > 0)
			{
				field[nx][ny] = h;
				qx.push(nx);
				qy.push(ny);
			}
		}
	}
}

int main()
{
	ifstream in("boxes.in");

	int tc;
	in >>tc;
	while (tc--)
	{
		int N;
		in >>N;
		assert(N <= 25);

		field.assign(102, vector<int>(102, 0));
		int height = 1;
		for (int i = 0;i < N;i++, height++)
		{
			int x1, y1, x2, y2;
			in >>x1>> y1>> x2>> y2;
	
			assert_coord(x1);
			assert_coord(x2);
			assert_coord(y1);
			assert_coord(y2);
			assert(x2 > x1);
			assert(y2 > y1);

			int cur_height = 0;
			for (int x = x1;x < x2;x++)
				for (int y = y1;y < y2;y++)
					field[x][y] = height;
		}

		height = -1;
		for (int x = 0;x < field.size();x++)
			for (int y = 0;y < field[0].size();y++)
				if (field[x][y] > 0)
					bfs(x, y, height--);

		int res = 0;
		for (int h = height;h < 0;h++)
		{
			int cur = 0;
			for (int x = 0;x < field.size();x++)
				for (int y = 0;y < field[0].size();y++)
					cur += field[x][y] == h;
			res = max(cur, res);
		}
		cout <<res <<endl;
	}

	return 0;
}