Mine Sweeper II 做题记录

扫雷地图是一张 $n$ 行 $m$ 列的网格，其中每个格子是地雷或空地。每个空地会显示一个数字代表与它相邻的雷的数量（两个格子相邻当且仅当它们共用一个顶点或一条边，不在边界上的格子与恰好 $8$ 个格子相邻）。 在一次操作中，你可以将一个地雷改成空地，或将空地改成地雷。 给定两张扫雷地图 $A$ 和 $B$，你需要对 $A$ 进行不超过 $\lfloor\frac{nm}{2}\rfloor$ 次操作，使得 $A$ 所有空地上的数字之和等于 $B$ 所有空地上的数字之和。

不难发现，对于一张给定的地图，数字的和有两种计算方式：

• 与每个空地格子相邻的地雷格子个数的和；
• 与每个地雷格子相邻的空地格子个数的和；

所以若把整个地图取反，即空地都变成地雷，地雷都变成空地，那么数字和不变。

设 $B$ 取反之后的地图是 $B'$，把 $A$ 变成 $B$ 的最小操作次数是 $x$，把 $A$ 变成 $B'$ 的最小操作次数是 $y$，那么由于 $x+y\le nm$，所以根据抽屉原理，有 $\min(x,y)\le \lfloor\frac{nm}{2}\rfloor$。所以把 $A$ 变成 $B$ 和 $B'$ 中需要更少次操作的即可。