Задача D. Шахматный детектив ≡
| Автор: | Седьмая Всероссийская Командная олимпиада школьников по программированию | Ограничение времени: | 2 сек | |
| Входной файл: | chess.in | Ограничение памяти: | 64 Мб | |
| Выходной файл: | chess.out |
Условие
Известный частный сыщик поставил чашку с чаем на специальную подогревающую подставку, питающуюся от USB-порта его компьютера, и приступил к обдумыванию очередного запутанного преступления. Через пару часов раздумий он понял, что для разгадки этого дела достаточно определить, была ли на месте преступления шахматная доска.
Недавно он получил по электронной почте фотографию места преступления. Подозрительный фрагмент (тот, на котором изображен предмет, похожий на шахматную доску) уже был скопирован в отдельный файл, но вдруг выяснилось, что, поскольку фотография была сжата с потерей качества, некоторые пиксели на ней из белых или черных стали серыми. Таким образом, определение того, является ли сфотографированный предмет шахматной доской, стало намного более сложным.
Все усложняется тем, что на фотографию могла попасть не вся шахматная доска, а лишь ее часть. Например, на приведенном рисунке на фотографию попала часть доски, у которой каждое поле имеет длину стороны, равную трем пикселям.
Помогите частному сыщику в расследовании преступления. Напишите программу, которая определит, может ли заданный фрагмент фотографии быть изображением части шахматной доски, и, если может, восстановит изображение шахматной доски до сжатия.
Шахматная доска — это квадрат, разбитый на х2 (для некоторого х) равных квадратов — полей. Стороны полей параллельны сторонам изображения. Длина стороны каждого поля шахматной доски выражается целым числом пикселей. Все пиксели, принадлежащие одному полю, покрашены в один и тот же цвет — черный или белый. При этом соседние поля (поля, имеющие общую сторону) покрашены в различные цвета.
Формат входного файла
Первая строка входного файла содержит два целых числа: m и n — размеры фрагмента фотографии в пикселях. Следующие m строк содержат по n символов каждая, j-й символ i-й строки соответствует пикселю с координатами (i,j). Символ "." (точка) означает белый пиксель, символ "*" - черный, символ "?" — серый.Формат выходного файла
Если заданный фрагмент фотографии может быть изображением части шахматной доски, выведите в выходной файл слово "YES". После этого выведите m строк по n символов в каждой. Они должны содержать изображение соответствующей части шахматной доски в том же формате, что и во входном файле, только серые пиксели должны быть заменены на белые или черные. Если решений несколько, выведите любое. В противном случае выведите в выходной файл слово "NO".Ограничения
1 ≤ m, n ≤ 250Примеры тестов
| № | Входной файл (chess.in) |
Выходной файл (chess.out) |
|---|---|---|
| 1 |
|
|
| 2 |
|
|