配点: 100 点
問題
JOI 你和家人一起来到了海滩。游了那么久,JOI也累了,接下来就去海边玩起了堆沙堡的游戏。过了一会儿,当JOI玩腻了沙子时,他独自离开城堡,又去海里游泳了。
JOI 你建造的城堡位于沙滩的矩形区域内。这个长方形的区域被划分为北、南、东、西四个正方形。每个方格要么是 JOI 创建的城堡的一部分(以下称为“城堡方格”),要么不是 JOI 创建的城堡的一部分(以下称为“空地方格”)。每个城堡方块都有一个值,称为“力量”。 1 以上 9 以下整数是固定的。矩形区域的外边缘,即与外界接触的细胞上没有城堡细胞。
最终,潮水来了,海浪开始涌入矩形区域。海浪 1 每当城堡涌入时,所有满足以下条件的城堡方格都会立即倒塌,变成空地。
状况:周围 8 一个方格(北、南、东、西、东北、西北、东南、西南方向的相邻方格)内的空地方格数量大于或等于该方格的强度值。 浪潮一退去,下一波浪潮就会涌来。
如果足够多的海浪袭来,整个城堡就会倒塌,或者即使海浪来了,也只会留下坚固的部分。 1 津茂城将进入一种不会倒塌的状态。1 求导致至少一个城堡方格倒塌的波浪到来的次数。 在
入力
输入是 由 1 + H 行组成。
1 行中,2 整数 H, W (2 \leqq H \leqq 1000,2 \leqq W \leqq 1000)以空格作为分隔符。这意味着矩形面积是 H 行,横 W 栏目 表示被划分为 H \times W 个方格。矩形的垂直方向为南北方向,水平方向为东西方向。
继续
每条 H 行都有 W 写着一串字母,代表第一波袭击之前矩形区域的状态。H 行 i 从该行的左侧开始 j 第一个字符(
如果矩形区域从北起第 i 行和从西起第 j 列是空格,则1 \leqq i \leqq H,1 \leqq j \leqq W) 是空格。 . (句号)。如果是城堡广场 1, 2, \ldots, 9 并代表该质量的强度。
矩形区域的外边缘都是空白区域。也就是说,对于所有输入,1 行或 H 本行及每行从左开始的字符 1 th 或
第 W 个字符全部 . 。
在给定的输入数据中,输入 1 所以 H \leqq 50,W \leqq 50 满意。
出力
1 摧毁 3 个或更多城堡方格的波浪将会出现的次数。 输出为 1 行。 在
入力例 1
5 6 ...... .939.. .3428. .9393. ......
出力例 1
3
入出力例 1 中,第一波的强度为 3 的城堡方块全部倒塌, 状态变为
...... .9.9.. ..428. .9.9.. ......
。
在下一波中,强度 2 的城堡广场倒塌,
...... .9.9.. ..4.8. .9.9.. ......
。
在下一波中,强度 4 的城堡广场倒塌,
...... .9.9.. ....8. .9.9.. ......
。
后续的波浪不会摧毁城堡广场。因此答案是 3 。
入力例 2
10 10 .......... .99999999. .9.323239. .91444449. .91444449. .91444449. .91444449. .91232329. .99999999. ..........
出力例 2
35