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 自动生成**

### Sample Explanation 1 入出力例 $ 1 $ においては，初めに押し寄せる波で強度 $ 3 $ の城マスがすべて崩壊し， ``` ...... .9.9.. ..428. .9.9.. ...... ``` という状態になる． 次に押し寄せてくる波では強度 $ 2 $ の城マスが崩壊し， ``` ...... .9.9.. ..4.8. .9.9.. ...... ``` という状態になる． 次に押し寄せてくる波では強度 $ 4 $ の城マスが崩壊し， ``` ...... .9.9.. ....8. .9.9.. ...... ``` という状態になる． これ以降の波が城マスを崩すことはない．よって答えは $ 3 $ である． - - - - - -