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.