AT_joi2015yo_e.砂の城 (Sandcastle)

JOI 君和家人去海边游泳。他游得太久累坏了，决定改在沙滩上建一个沙堡。玩了一会儿，JOI 君开始觉得无聊，把沙堡丢在一边，又跑去海里继续游泳了。

JOI 君的沙堡建在沙滩上的一个矩形区域内，这个区域被划分成一个有规则的网格。每个格子要么是沙堡的一部分（称为「城格」），要么不是（称为「空地格」）。每个城格都有一个强度值，范围从 $1$ 到 $9$。值得注意的是，整个矩形区域的边缘不可能有城格。

随着潮水的上涨，海浪开始冲击这个矩形区域。每当一波浪涌来时，所有满足以下条件的城格会被同时摧毁，变成空地格：

• 条件：该格子周围 $8$ 个相邻格子（上下左右以及四个对角方向）中空地格的数量等于或超过该格子的强度值。

每波浪退却后，紧接着就有新的波浪拍打过来。经过足够的波浪冲击后，沙堡要么被完全摧毁，要么剩下的部分足够坚固，不会再有城格受损。请计算能使至少一个城格崩塌的波浪次数。

输入包含 $H + 1$ 行。

第一行有两个整数 $H$ 和 $W$，表示矩形区域按网格划分为 $H$ 行 $W$ 列（$2 \leq H \leq 1000$，$2 \leq W \leq 1000$）。矩形区域的行方向为南北向，列方向为东西向。

接下来的 $H$ 行表示初始状态下矩形区域的布局。每行有 $W$ 个字符，如果字符是 .，则为空地格；如果是 1 至 9 中的一个数字，则为城格，其强度即为数字的取值。

矩形区域的边缘全是空地格，这意味着所有输入中，第一行和最后一行的所有字符，以及每一行的第一个和最后一个字符都是 .。

在给出的样例数据中，满足 $H \leq 50$ 和 $W \leq 50$。

输出一个整数，代表能让至少一块城格被冲毁的波浪次数。

样例解释 1

在样例 1 中，第一波浪会摧毁所有强度为 $3$ 的城格，变为：

......
.9.9..
..428.
.9.9..
......

第二波浪会摧毁所有强度为 $2$ 的城格，变为：

......
.9.9..
..4.8.
.9.9..
......

第三波浪会摧毁所有强度为 $4$ 的城格，变为：

......
.9.9..
....8.
.9.9..
......

之后，再没有波浪能够摧毁城格。因此，冲击次数为 $3$。

本翻译由 AI 自动生成