double arrow

Эффективные структуры данных

 

5. Поиск прямоугольников

(Время: 0,5 сек. Память: 16 Мб Сложность: 34%)

На поле NxM клеток (N строк и M столбцов) положили K прямоугольников один поверх другого в случайном порядке. Длины сторон прямоугольников выражаются целым числом клеток. Прямоугольники не выходят за границы поля. Границы прямоугольников совпадают с границами клеток поля.

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

Требуется написать программу, которая определит положение и размеры прямоугольников. Гарантируется, что во входных данных содержится информация, которой достаточно для однозначного определения размеров прямоугольников.

Входные данные

Входной файл INPUT.TXT содержит в первой строке целые числа N, M, K (1<=N<=200, 1<=M<=200, 1<=K<=255). Далее следует N строк по M чисел в каждой — содержимое таблицы. Все числа в таблице целые, находятся в диапазоне от 0 до K включительно.

Выходные данные

Выходной файл OUTPUT.TXT должен содержать K строк. Каждая строка должна описывать соответствующий ее номеру прямоугольник четырьмя числами X1 Y1 X2 Y2 (X1 и Y1 должны описывать координаты левого нижнего угла прямоугольника, а X2 и Y2 — координаты правого верхнего угла). Числа должны разделяться пробелом.




Начало координат расположено в левом нижнем углу таблицы. Таким образом, координаты левого нижнего угла поля — (0,0), правого верхнего — (M,N).

Пример

INPUT.TXT OUTPUT.TXT
4 5 2 0 2 2 2 2 0 2 2 2 2 1 1 2 2 2 1 1 0 0 0 0 0 2 2 1 1 5 4

Решение:

var

xmin,xmax,ymin,ymax:array[1..255] of integer;

x,y,w,h,k,i,j:integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

 

read(h,w,k);

for i:=1 to k do

begin

xmin[i]:=w;

ymin[i]:=h;

end;

 

for y:=h downto 1 do

for x:=1 to w do

begin

read(j);

if j>0 then

begin

if x<xmin[j] then xmin[j]:=x;

if y<ymin[j] then ymin[j]:=y;

 

if x>xmax[j] then xmax[j]:=x;

if y>ymax[j] then ymax[j]:=y;

end;

end;

 

for i:=1 to k do writeln(xmin[i]-1,' ',ymin[i]-1,' ',xmax[i],' ',ymax[i]);

close(output);

end.

 






Сейчас читают про: