Архив Зеленоградского турнира

Головоломка "сапер" основана на широко известной игре "Minesweeper", имеющейся почти у всех обладателей MS Windows, начиная, кажется, еще с версии 2.0. Цель ее проста: исходя из данных ключевых чисел, восстановить расположение мин в прямоугольнике. Каждое ключевое число показывает, сколько соседних с ним клеток (из восьми) занято минами. Мины расположены по одной в каждой клетке, а в клетке с числом мин не бывает. В головоломке, в отличие от игры, нельзя "щелкнуть" по клетке и в результате убедиться, что она пуста (или, наоборот, напороться на мину и затем начинать все сначала). В головоломке заранее оговаривается общее число мин, скрытых на данном поле. Эта информация может оказать существенную помощь в решении, а часто без нее решение перестает быть единственным.

Рассмотрим процесс решения на примере небольшого квадрата. Общее количество мин в нашем случае равно 19. Будем обозначать, как обычно, строки цифрами, а столбцы - буквами. Мины мы станем отмечать значками, а клетки, в которых мина находиться не может - зарисовывать голубым цветом. Процесс решения этой головоломки, как и многих других, складывается из отдельных рассуждений - мелких шагов. Все понимают, что если количество пустых клеток вокруг числа равно ему самому, то можно сразу заполнить все эти клетки минами. Но в профессионально сделанных "саперах" это редко встречается, как взятие фигуры на первом ходу в шахматной двухходовке. Поэтому первые шаги, как правило, должны быть более тонкими. Будьте внимательны!

Рассмотрим число 2 на клетке h3. Оно дает информацию, что в четырех клетках gh2 и gh4 расположены ровно две мины. Число 3 на g3 дает информацию, что в двух клетках f3 и f4 ровно одна мина (так как в остальных клетках, окружающих его - две мины). Отсюда можно сделать вывод, что остальные клетки, окружающие единицы на e3 и е4 - пусты. Закрашиваем их голубым цветом.

После этого две мины вокруг клетки d4 и три мины вокруг клетки е5 восстанавливаются однозначно.

Остальные клетки вокруг f5 можно отметить, как пустые, что позволяет поставить однозначно две мины рядом с h6 - на h5 и h7.

Каждый новый шаг тут же дает дополнительные возможности для осуществления новых шагов. Отмечаем пустые клетки вокруг g7, добавляем мину на е7 (чтобы вокруг d6 было ровно три мины). Отмечаем, что клетка f3 пуста, и как следствие - все оставшиеся клетки вокруг f2 заполнены минами.

Отмечаем мину на d1 и на b6, красим голубым h2, затем ставим мину на h4.

Когда кончились элементарные соображения, для продолжения решения необходимо снова использовать более тонкие рассуждения. Рядом с b7 ровно на одну мину больше, чем рядом с а7, эта мина может быть только на с8. Остальные клетки, соседние с с7, пусты, как и е8.

Цифра 4 на с2 означает, что в клетках b1, b3, и с1 имеется пара мин, которые вместе с миной на с3 полностью "обеспечивают" тройку на b2. Поэтому клетки а2 и а3 пусты. То есть мина для а1 находится в b1.

В клетках b3 и b4 ровно одна мина (за счет тройки в с4), поэтому мина есть в а5 (за счет двойки в а4).

Осталось совсем немного - обозначить пустые клетки вокруг b5, мины в а8 и b3, пустую клетку с1. И обязательно убедиться, что в решении нет ошибок.

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

t – число тестов, затем следуют t тестов. [t <= 500]
Каждый тест начинается с трех чисел H, W и N равных соответственно высоте, длине поля и количеству мин [5 <= H, W <= 50] [1 <= N <= H*W]
Затем следуют ровно H строк каждая из которых состоит из W символов.
Описание поля состоит из символов '1'-'8' - количество мин в соседних клетках и '.' - пустая клеточка. Вы можете быть уверены, что никакие другие символы в описании поля не присутствуют.

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

Для каждого теста необходимо на отдельной строчке букву Y если вы хотите решать этот тест или же N в противном случае. Далее в том случае если вы ответили Y, необходимо вывести поле, того же размера, что и в тесте, с проставленными на нем минами. Мины задаются символом 'X'. Количество мин должно равняться количеству мин заданных в данном тесте и располагаться они должны в клетках заданных '.' в исходном тесте.

Начисление очков

Общее число очков, полученных за решение, равно сумме очков за каждый тест. Количество очков за тест равно числу клеточек с числами вокруг которых мины расставлены правильно (количество мин в соседних клеточках равно заданному числу) из этой суммы вычитается количество клеточек вокруг, которых мины расставлены неправильно (количество мин в соседних клеточках не равно заданному числу). Если количество очков за тест получается отрицательным, то число очков за этот тест будет равно нулю. В том случае если тест решен полностью правильно, то количество очков полученных за этот тест умножается на 10.
Дополнительная информация: Если количество очков равно xxx.aaa, то aaa показывает количество полностью правильных решений.

Пример

2
8 8 19
........
2323..2.
..23...2
.3..33..
2.321...
....1.32
.3...3..
1...2..2
6 6 6
111.1.
1.2121
112.21
..112.
122111
1..1..

Y
X.X.....
2323X.2X
.X23XX.2
X3X.33.X
2.321X.X
.XX.1.32
.3...3X.
1X.X2XX2
Y
111X1.
1X2121
112X21
..112.
122111
1.X1XX

Первый тест решен полностью правильно и за него будет начислено: 23*10 = 230 очков. За второй тест количество очков будет равно 10-15 = -5, то есть, начислено будет 0.