В секретном-секретном городе, в секретном-секретном районе, на секретном-секретном заводе производится секретные-секретные секреты. Сверхсекретный спутник-шпион с помощью секретного оборудования в засекреченный момент времени сделал секретнейший снимок. Для успешного проведения операции по скрытому воздействию на секреты наиболее вероятного противника, секретный снимок необходимо правильно интерпретировать.
Снимок представляет собой матрицу W на H клеток, в каждой клетке которой записан один из следующих символов:
. | Свободный, проходимый участок |
- | Непроходимое горизонтальное заграждение (перегородка) |
| | Непроходимое вертикальное заграждение (перегородка) |
+ | Непроходимое соединение горизонтальной и вертикальной перегородок (крестовина) |
# | "Секрет" |
Секрет представляет собой обычную крестовину (+), в центре которой находится один из объектов интереса спецоперации. При этом объект интереса доступен с любой из четырёх сторон крестовины.
Секретные агенты, к сожалению, не умеют проходить сквозь перегородки, а ломать их запрещено. Но это их единственное ограничение — на то они и секретные агенты.
Чтобы пояснить возможности агентов, ниже приведён ряд примеров:
+-+-+ |-+-|
|#|#| |#|#|
+---+ +-+-+
В первой схеме агент может свободно расхаживать между секретами через дыру в нижней стыковке вертикальной и горизонтальной перегородок. Во второй схеме дыра заделана крестовиной и секреты не соединены. Дырами же в верхней части схемы пользоваться нельзя — чтобы не рисковать операцией, спецагентам строго-настрого запрещено выходить за пределы сфотографированной области. Вы же для удобства можете считать, что сфотографированный участок
окружён рамкой из крестовин.
+-+...+-+ +-+...+-+
|#+---+#| |#+-+-+#|
+---+---+ +---+---+
Здесь аналогично, в первом случае секреты соединены, а во втором — нет.
+-----+ +++++++
+#####+ +#####+
+++++++ +++++++
Если вспомнить, что секрет представляет собой особую разновидность крестовины, то станет понятно, почему на первой схеме все секреты соединены, а на второй
соединены только соседние.
Вам необходимо построить граф связности секретов, то есть такой граф, в котором множество вершин — это множество секретов, а ребро (a, b) присутствует тогда и только тогда, когда секретный агент может пробраться от секрета a к секрету b, не ломая перегородок и не выходя за пределы
сфотографированной области.
Ограничения
Размеры снимка не превосходят 1000 на 1000 символов.
Известно, что на снимке находится не более 100 секретов.
Исходные данные
Дано H строк длины W символов каждая. Они задают секретный снимок
размером W на H.
Результат
Вывести таблицу смежности графа связности секретов. Секреты нумеруются сверху вниз, справа налево. Ячейка из i-й строки и j-го столбца должна содержать 1, если i-й и j-й секрет соединены, и 0, если не соединены.
Пример
исходные данные | результат |
---|
+------+
|#+-+--|
-++#|..|
##..|#.|
-+--+--+ | 10100
01010
10100
01011
00011 |
Автор задачи: Павел Егоров
Источник задачи: IX Чемпионат Урала по спортивному программированию. Екатеринбург, УрГУ, 19-24 апреля 2005 г.