ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат Урала 2005 Тур II

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

H. Конфиденциально!

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
В секретном-секретном городе, в секретном-секретном районе, на секретном-секретном заводе производится секретные-секретные секреты. Сверхсекретный спутник-шпион с помощью секретного оборудования в засекреченный момент времени сделал секретнейший снимок. Для успешного проведения операции по скрытому воздействию на секреты наиболее вероятного противника, секретный снимок необходимо правильно интерпретировать.
Снимок представляет собой матрицу 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 г.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1367. Конфиденциально!