Карта шахти

Після нещодавньої крадіжки збірника задач для фіналу ACM ICPC (яку здійснив сумнозвісний британський супер-шпигун Джеймс Б. — ми вже повідомляли про це кілька тижнів тому), ACM вирішила зберігати всі майбутні збірники задач у будівлі з підвищеним рівнем безпеки. Рада з безпеки, відповідальна за створення цього нового сховища, запропонувала блискучу ідею побудувати його у вигляді гігантського лабіринту. В основі цього лабіринту — багато квадратних кімнат, розташованих у формі квадратної матриці, і всі кімнати з'єднані між собою низкою дверей. Пройти через ці кімнати — єдиний спосіб дістатися центру, де зберігаються збірники задач.

Очевидно, що пройти лабіринт, у якому всі кімнати з'єднані між собою, не дуже складно. Тому, щоб ускладнити завдання потенційним зловмисникам, деякі з кімнат заміновано. Якщо хтось входить до центральної кімнати сховища, що містить збірники задач, ці міни активуються. З цього моменту, як тільки хтось відчинить двері, що ведуть до замінованої кімнати, спрацьовує сигналізація, і всі захисні двері негайно закриваються, замуровуючи порушника. Таким чином, ACM може встановити, хто послав шпигуна, і дискваліфікувати всі команди від тієї країни.

Однак нещодавно рада з безпеки дізналася про новий сканувальний пристрій, який може виявляти міни після їх активації. Цей детектор можна використати у будь-якій кімнаті сховища: він вказує, чи є в одній з до восьми сусідніх кімнат міна. На жаль, рада вже замовила партію цих мін і не хоче визнавати, що це могло бути помилкою. Тому вони просто хочуть розташувати міни так, щоб покинути центр, користуючись лише пристроєм, було важко. Ви входите до команди, що будує сховище, щоб допомогти оцінити їхні проєкти.

Сховище має форму чотирикутника зі сторонами непарної довжини. Кожну кімнату в сховищі можна описати парою координат, які вказують горизонтальне та вертикальне зміщення від фіксованого кута будівлі. Кожна кімната має двері, що ведуть у сусідні кімнати; найголовніше, що детектор міни може знаходити міни у всіх до восьми суміжних кімнатах. Пристрій може лише сказати, чи є поряд міни, але не скаже, скільки їх.

Ваше завдання — створити спеціальну мапу для кожного макету сховища. На мапі позначте всі кімнати, яких можна безпечно досягти, якщо почати з центральної кімнати (яка гарантовано не містить міни), використовуючи новий детектор і таку просту стратегію: коли ви в кімнаті, де детектор показує відсутність поряд мін, шукайте у всіх прилеглих кімнатах. Інакше не ризикуйте — не просувайтесь далі з цієї кімнати (хоча ви можете потім потрапити до однієї із сусідніх кімнат іншим «безпечним» шляхом).

Таким чином, якщо шпигун перебуває в кімнаті, не суміжній із мінами, він зможе потрапити до всіх довколишніх кімнат — таку кімнату позначте символом ".". Якщо шпигун потрапляє до кімнати, яка прилягає хоча б до однієї міни, він відступає — ці кімнати позначте символом "#". Щоб перевірити вашу роботу, рада з безпеки також просить вас позначити положення кожної міни символом "*". Нарешті, всі інші кімнати слід позначити символом "?".