Районно-городские командные соревнования

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

Поле для игры "Сапер" состоит из прямоугольной сетки, одна или более ячеек которой заминированы. В начале игры все клетки поля закрыты. Цель игры состоит в том, чтобы открыть все незаминированные ячейки. Если открывается ячейка с миной, то игра заканчивается и игрок проигрывает. Ячейка может находиться в одном из трех состояний: закрыта, открыта/пустая или помечена флажком как заминированная.

Когда игрок открывает незаминированную клетку, в ней отображается число мин, спрятанных в соседних клетках. Это число помогает игроку выяснить расположение мин. Соседними считаются клетки, образующие квадрат `3\ times\ 3` с открываемой клеткой в центре. В зависимости от местоположения клетки она может иметь от 3 до 8 соседних ячеек. На рис. 1 показаны две мины с координатами (3,1) и (3,2) и число соседствующих мин для всех оставшихся клеток.

Неопытный игрок, имея эту информацию, поступает следующим образом. Первым делом он выбирает одну ячейку из полностью закрытого поля. Если там находится мина, игра заканчивается. Иначе, он открывает эту клетку и до тех пор, пока возможно, применяет два следующих правила для разминирования оставшегося поля. Пусть `(x,\ y)` – координаты открытой ячейки, и пусть `f`, `c` и `m` – число помеченных флажком, закрытых и заминированных соседних с `(x, y)` клеток.

Отметим, что после успешно открытой первой клетки, неопытный игрок никогда не открывает и не помечает флагом ячейки, кроме как в соответствии с правилами 1 и 2. Это означает, что он может зайти в тупик. Когда такое происходит, игра останавливается. Никаких дополнительных предположений о расположении мин не делается, никакие более сложные правила, позволяющие безопасно открыть оставшиеся клетки не применяются.

На рис. 2 показано использование этих правил для позиции на рис. 1.

Рис. 2a содержит позицию на доске после начального вскрытия клетки `(1,\ 2)`. Здесь можно применить правило 1, поскольку (0 помеченных флагом = 0 заминированных соседних) и игрок открывает соседние клетки `(1,\ 1)`, `(1,\ 3)`, `(2,\ 1)`, `(2,\ 2)` и `(2,\ 3)`, как показано на рис. 2b.

Далее игрок рассматривает ячейку `(2,\ 1)` и применяет правило 2 (0 помеченных флагом + 2 закрытых = 2 заминированных) чтобы пометить ячейки `(3,\ 1)` и `(3,\ 2)` как заминированные. Результат приведен на рис. 2c.

Окончательно, рассматривая клетку `(2,\ 3)`, игрок вновь применяет правило 1 и открывает ячейку `(3,\ 3)`, поскольку `(2,\ 3)` соседствует ровно с одной миной, и ячейка `(3,\ 2)` уже помечена флажком. Теперь все ячейки без мин открыты, игра завершается победой игрока.

Как было сказано выше, этих двух правил недостаточно, чтобы открыть целиком любое поле, начиная с любой клетки. Вновь рассмотрим позицию на рис. 1. Если игрок начнет открывать поле с клетки `(2,\ 2)`, то возникнет ситуация как на рис. 3. Игрок не сможет продвинуться дальше, поскольку ни правило 1, ни правило 2 не позволяют открыть или пометить флажком ни одну из клеток. В этом случае игрок застопорился, имея шесть закрытых незаминированных клеток.

Вы должны написать программу, которая анализирует игровое поле и определяет наименьшее число незаминированных клеток, которые возможно останутся закрытыми после того, как неопытный игрок выполнит вышеописанные действия. Для игрового поля на рис. 1 верным ответом будет 0.

Входной файл содержит одно или более игровых полей, за которыми следует строка с двумя нулями. Описание поля начинается с двух целых чисел `r` и `c` – число строк и столбцов поля; `r` и `c` всегда больше либо равны 3. Число ячеек любого поля не больше 40. Последующие данные являются графическим представлением игрового поля: латинская прописная буква 'M' означает мину, и точка '.' означает пустую клетку. На любой доске всегда имеется хотя бы одна мина и хотя бы одна пустая клетка.

Для каждого набора данных, выведите одну строку, содержащую наименьшее число закрытых незаминированных клеток для этого поля.

3 3
...
...
MM.
3 4
M.M.
.M.M
M.M.
7 5
.....
.....
MMM..
M.M..
MMM..
.....
.....
4 4
...M
....
....
M...
0 0

0
5
1
0