Поиск прямоугольников
(Время: 0,5 сек. Память: 16 Мб Сложность: 34%)
На поле N×M клеток (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 |
|---|
| 1 | 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 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
