Задача E. Водовод на о. Русский ≡

Условие

При строительстве нового кампуса ДВФУ на о. Русском по дну пролива был проложен водовод с материка на остров. К сожалению, после завершения строительства все чертежи были утеряны, а строители разъехались. Чтобы восстановить карту водовода, были проведены гидрографические работы.

Была составлена прямоугольная карта залива, разбитая на ячейки. Левый столбец ячеек примыкает к материку, а правый — к острову. По результатам работ каждая ячейка была помечена символом '#' (по ячейке может проходить водовод) или '.' — водовод по ячейке точно не проходит.

Известно, что водовод представляет собой последовательность ячеек, имеющих общую сторону. Первая его ячейка находится в первом столбце клеток карты, последняя — в последнем. Водовод не проходит дважды через одну и ту же ячейку.

Дана карта, составленная по результатам работ. Необходимо определить, можно ли однозначно восстановить водовод по карте.

Формат входного файла

Первая строка входного файла содержит размеры карты — высоту H и ширину W. Далее следует H строк по W символов в каждой — карта.

Формат выходного файла

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

Если существует несколько способов восстановить положение водовода, то выведите сначала слово MULTIPLE, а затем два различных описания водовода в любом порядке. Если существует более двух вариантов, выведите любые два из них.

Если водовод восстановить невозможно, выведите единственное слово NO.

Ограничения

2 ≤ H, W ≤ 200

Примеры тестов

4 5
...##
##...
.####
...#.

YES
6  2 1  2 2  3 2  3 3  3 4  3 5 

3 6
#.###.
###.##
......

MULTIPLE
9  1 1  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6

3 6
..###.
###.##
..###.

MULTIPLE
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  3 3  3 4  3 5  2 5  2 6

3 3
...
.##
...

NO

Разбор

Построим граф, вершинами которого будут занятые клетки, а ребро между двумя вершинами будет в том случае, если две клетки имеют общую сторону. Добавим в граф две вершины. Первую соединим со всеми занятыми клетками в первой колонке, а вторую — со всеми занятыми в последней. Каждому водопроводу будет соответствовать путь между двумя добавленными нами вершинами и наоборот. А значит, задачу можно переформулировать: "определить, существует ли между двумя вершинами в графе путь, и если да, то единственен ли он". В задаче требуется также вывести на печать найденные пути.

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

Рассмотрим всё множество путей между заданными вершинами. Уберём рёбра в начале, общие для всех путей. Для первой вершины, в которой имеется "развилка", заметим: если запустить второй поиск в глубину, который перебирает рёбра каждой вершины в противоположном порядке, то на "развилке" будет выбрано другое ребро. Из этого другого ребра мы всё равно попадём в конечную вершину, поскольку ребро по построению принадлежало некоторому искомому пути.

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