Олимпиадный тренинг

Задача . F. Непереводимое название


Задача

Темы: Конструктив реализация поиск в глубину и подобное графы *2700 2-sat снм

У Алисы есть пустое поле из \(n\) строк и \(m\) столбцов. Некоторые клетки этого поля помечены, и ни одна помеченная клетка не касается края поля. (Две клетки считаются соседними, если они касаются по стороне.)

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

  • в каждой непомеченной клетке записано либо \(1\), либо \(4\);
  • в каждой помеченной клетке записана сумма чисел всех соседних непомеченных клеток (если у помеченной вершины нет соседних непомеченных, то сумма равна \(0\));
  • в каждой помеченной клетке записанное число делится на \(5\).
Не придумав ничего, Алиса решила попросить помощи у Боба. Помогите Бобу найти любое подходящее заполнение поля, или определить, что такого поля не существует.
Входные данные

В первой строке заданы два целых числа \(n\) и \(m\) (\(1 \leq n, m \leq 500\)) — количество строк и столбцов поля, соответственно.

Далее следуют \(n\) строк, каждая состоит из \(m\) символов. Каждый символ — это «.» или «X» — непомеченная или помеченная клетка, соответственно. Ни одна помеченная клетка не касается краев поля.

Выходные данные

Выведите «NO», если не существует подходящего заполнения. В противном случае выведите «YES». Далее выведите \(n\) строк по \(m\) целых чисел через пробел — числа в клетках поля.

Примечание

Можно показать, что во втором примере не существует подходящего заполнения.


Примеры
№Входные данныеВыходные данные
1 
5 5
.....
.XXX.
.X.X.
.XXX.
.....
 
YES
4 1 4 4 1
4 5 5 5 1
4 5 1 5 4
1 5 5 5 4
1 4 4 1 4
2 
5 5
.....
.XXX.
.XXX.
.XXX.
.....
 
NO
3 
3 2
..
..
..
 
YES
4 1
4 1
1 4
4 
9 9
.........
.XXXXX.X.
.X...X...
.X.XXXXX.
.X.X.X.X.
.X.XXX.X.
.X.....X.
.XXXXXXX.
.........
 
YES
4 4 4 1 4 1 4 1 4
1 5 5 5 5 5 4 10 1
4 5 1 4 1 5 4 4 4
4 5 1 5 5 0 5 5 1
4 5 1 5 4 5 1 5 4
4 5 1 5 5 5 4 5 1
1 5 4 4 1 1 4 5 1
4 5 5 5 5 5 5 5 4
1 1 1 1 4 4 1 1 4

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++5
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет