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