Матч 211, Графическая маска (grafixMask)

Дивизион 1, Уровень 2

Имеется полотно прямоугольной формы размером 400 на 600 точек. На нем рисуют набор прямоугольников, координаты которых заданы в массиве rectangles. Дыркой называется максимальное множество соседних точек, не принадлежащих ни одному прямоугольнику. Две точки называются соседними, если они прилегают друг к другу по горизонтали или по вертикали.

Левый рисунок содержит две дырки, а правый – девять.

Необходимо найти все размеры дырок и вывести их в возрастающем порядке.

Класс: grafixMask

Метод: vector<int> sortedAreas(vector<string> rectangles)

Ограничения: rectangles содержит от 1 до 50 элементов, каждый из которых имеет формат “ROW COL ROW COL”, 0 £ ROW £ 399, 0 £ COL £ 599.

Вход. Массив строк rectangles, каждый элемент которых содержит координаты противоположных углов прямоугольника в формате “<строка> <столбец> <строка> <столбец>”.

Выход. Массив целых чисел, содержащий размеры всех дырок в возрастающем порядке после нанесения на полотно всех прямоугольников.

Пример входа

rectangles

{"0 292 399 307"}

{"48 192 351 207", "48 392 351 407", "120 52 135 547", "260 52 275 547"}

{"0 192 399 207", "0 392 399 407", "120 0 135 599", "260 0 275 599"}

Пример выхода

{116800, 116800}

{22816, 192608}

{22080, 22816, 22816, 23040, 23040, 23808, 23808, 23808, 23808}

РЕШЕНИЕ

поиск в глубину + структуры данных

Будем трактовать точки полотна, покрытые хотя бы одним прямоугольником, водой, а точки, не покрытые ни одним прямоугольником, сушей. Тогда дырками будут являться острова. Задача сводится к нахождению количества островов и вычислению их размеров, что решается при помощи поиска в глубину.

При запуске процедуры поиска в глубину используется стек. Размеры полотна достаточно большие, поэтому потребуется большое количество памяти. В связи с архитектурой компьютерных программ, память, доступная для рекурсивных вызовов, мала. Поэтому следует брать память из кучи, что можно реализовать только используя непосредственно структуру данных stack.

ПРОГРАММА

Эта программа работает на полотне небольшого размера. При запуске программы на полотне 400 * 600 происходит переполнение стека.

#include <cstdio>

#include <vector>

#include <memory>

#include <string>

#include <algorithm>

using namespace std;

bool m[400][600];

int i, j, k;

int _top, _left, _down, _right;

int dfs(int i,int j)

{

if ((i < 0) || (i >= 400) || (j < 0) || (j >= 600)) return 0;

if (m[i][j] == true) return 0;

m[i][j] = true;

return 1 + dfs(i-1,j) + dfs(i+1,j) + dfs(i,j-1) + dfs(i,j+1);

}

class grafixMask

{

public:

vector<int> sortedAreas(vector<string> rectangles)

{

vector<int> res;

memset(m,false,sizeof(m));

for(i = 0; i < rectangles.size(); i++)

{

sscanf(rectangles[i].c_str(),"%d %d %d %d",&_top,&_left,&_down,&_right);

for(j = _top; j <= _down; j++)

for(k= _left; k <= _right; k++) m[j][k] = true;

}

for(j = 0; j < 400; j++)

for(k = 0; k < 600; k++)

{

if (m[j][k] == true) continue;

res.push_back(dfs(j,k));

}

sort(res.begin(),res.end());

return res;

}

};

Реализация программы с использованием памяти из кучи посредством структуры данных stack.

#include <cstdio>

#include <vector>

#include <memory>

#include <string>

#include <stack>

#include <algorithm>

using namespace std;

bool m[400][600];

int i, j, k;

int _top, _left, _down, _right;

stack<pair<int,int> > s;

pair<int,int> node;

int dfs(int i,int j)

{

int res = 0;

s.push(make_pair(i,j));

while(!s.empty())

{

node = s.top(); s.pop();

if ((node.first < 0) || (node.first >= 400) ||

(node.second < 0) || (node.second >= 600)) continue;

if (m[node.first][node.second]) continue;

m[node.first][node.second] = true;

res++;

s.push(make_pair(node.first+1,node.second));

s.push(make_pair(node.first-1,node.second));

s.push(make_pair(node.first,node.second+1));

s.push(make_pair(node.first,node.second-1));

}

return res;

}

class grafixMask

{

public:

vector<int> sortedAreas(vector<string> rectangles)

{

vector<int> res;

memset(m,false,sizeof(m));

for(i = 0; i < rectangles.size(); i++)

{

sscanf(rectangles[i].c_str(),"%d %d %d %d",&_top,&_left,&_down,&_right);

for(j = _top; j <= _down; j++)

for(k = _left; k <= _right; k++) m[j][k] = true;

}

for(j = 0; j < 400; j++)

for(k = 0; k < 600; k++)

{

if (m[j][k] == true) continue;

res.push_back(dfs(j,k));

}

sort(res.begin(),res.end());

return res;

}

};