本题没有可用的提交语言。

问题描述

扫雷游戏的一个变种几乎适用于所有计算机平台。您的雇主希望开发一个面向休闲玩家（而非专业玩家）的新版本。您的任务是编写一个程序，接收扫雷棋盘并返回休闲玩家尽力操作后仍未被揭开的非地雷格子的最小数量。以下是游戏规则和程序要求的详细说明。

棋盘结构

扫雷棋盘由矩形网格组成，其中包含一个或多个地雷格子。初始状态下所有格子都被覆盖（即空白）。游戏目标是揭开所有不含地雷的格子。若揭开地雷格子，则游戏失败。每个格子可能处于以下三种状态之一：

• 被覆盖
• 已揭开
• 被标记为地雷

游戏机制

1. 当玩家揭开一个非地雷格子时，该格子会显示其相邻地雷数量（相邻格子指以该格子为中心的$3×3$区域内的所有格子，边缘格子有$3-5$个相邻格子，内部格子有$8$个相邻格子）。

2. 休闲玩家按照以下规则操作：

   • 规则1：若某已揭开格子$(x,y)$周围标记的地雷数$f$等于实际地雷数$m$（即$f = m$），则揭开所有相邻的被覆盖格子
   • 规则2：若某已揭开格子$(x,y)$周围被覆盖格子数$c$与标记数$f$之和等于实际地雷数$m$（即$f + c = m$），则将相邻所有被覆盖格子标记为地雷

3. 玩家首次操作后，仅通过上述两条规则进行后续操作（不会主动猜测），因此可能陷入无法继续的状态。此时游戏结束，剩余未被揭开的非地雷格子即为最终结果。

示例说明

图1展示了一个棋盘示例，其中$(3,1)$和$(3,2)$为地雷格子。假设玩家首次揭开$(1,2)$：

1. 应用规则1（$0$标记=$0$地雷）揭开相邻的$(1,1),(1,3),(2,1),(2,2),(2,3)$
2. 对$(2,1)$应用规则2（$0$标记+$2$覆盖=$2$地雷）标记$(3,1),(3,2)$为地雷
3. 对$(2,3)$应用规则1（$1$标记=$1$地雷）揭开$(3,3)$ 此时所有非地雷格子均被揭开，玩家获胜。

若玩家首次选择$(2,2)$，则会陷入无法继续的状态，剩余$6$个被覆盖的非地雷格子。

输入格式

• 多组棋盘数据，以$0\ 0$结束
• 每组数据首行为行数$r$和列数$c$（$3 \leq r,c$，总格子数$\leq 40$）
• 接下来$r$行为棋盘布局：'M'表示地雷，'.'表示空格子
• 每组数据至少包含$1$个'M'和$1$个'.'

输出格式

对每组数据，输出休闲玩家最优操作后剩余被覆盖非地雷格子的最小数量

示例输入输出

输入示例：

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

关键要求

程序需计算所有可能的首次操作后，剩余被覆盖非地雷格子的最小值。例如图1所示棋盘，最优解为$0$（即存在某个首次操作可使玩家完全揭开所有非地雷格子）。