Автор: | И. Туфанов | Ограничение времени: | 2 сек | |
Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
Выходной файл: | output.txt | |||
Максимальный балл: | 100 |
При строительстве нового кампуса ДВФУ на о. Русском по дну пролива был проложен водовод с материка на остров. К сожалению, после завершения строительства все чертежи были утеряны, а строители разъехались. Чтобы восстановить карту водовода, были проведены гидрографические работы.
Была составлена прямоугольная карта залива, разбитая на ячейки. Левый столбец ячеек примыкает к материку, а правый — к острову. По результатам работ каждая ячейка была помечена символом '#' (по ячейке может проходить водовод) или '.' — водовод по ячейке точно не проходит.
Известно, что водовод представляет собой последовательность ячеек, имеющих общую сторону. Первая его ячейка находится в первом столбце клеток карты, последняя — в последнем. Водовод не проходит дважды через одну и ту же ячейку.
Дана карта, составленная по результатам работ. Необходимо определить, можно ли однозначно восстановить водовод по карте.
Первая строка входного файла содержит размеры карты — высоту H и ширину W. Далее следует H строк по W символов в каждой — карта.
Если положение водовода может быть однозначно восстановлено, то выведите сначала слово YES
,
а затем набор чисел, содержащих описание самого водовода.
Первое число в описании обозначает количество ячеек водовода, n, за которым следует
n пар чисел вида ri,ci, обозначающих номер строки и номер столбца очередной ячейки
(строки и столбцы нумеруются с единицы).
Если существует несколько способов восстановить положение водовода, то выведите сначала слово
MULTIPLE
, а затем два различных описания водовода в любом порядке.
Если существует более двух вариантов, выведите любые два из них.
Если водовод восстановить невозможно, выведите единственное слово NO
.
2≤H,W≤200
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|
4 |
|
|