分数: 300 点
问题陈述
给你一个正方形网格,其中 H 水平行和 W 垂直列,其中每个方块都漆成白色或黑色。
HW 字符来自 A_{11} to A_{HW} 代表方块的颜色。
A_{ij} is # 如果正方形位于 i从顶部开始的第行和 j从左边算起的第列是黑色的,并且 A_{ij} is . 如果该方块是白色的。
我们将重复执行以下操作,直到所有方块都变成黑色:
- 每个与黑色方块共享一条边的白色方块都会变成黑色。
查找将执行的操作数。 初始网格至少有一个黑色方块。
约束
- 1 \leq H,W \leq 1000
- A_{ij} is
#or.. - 给定的网格至少有一个黑色方块。
输入
输入由标准输入按以下格式给出:
H W
A_{11}A_{12}...A_{1W}
:
A_{H1}A_{H2}...A_{HW}
输出
打印将执行的操作数。
示例输入 1
3 3 ... .#. ...
示例输出 1
2
一次操作后,网格中除角之外的所有区域都会变黑。再进行一次操作后,所有的方块都会变成黑色。
示例输入 2
6 6 ..#..# ...... #..#.. ...... .#.... ....#.
示例输出 2
3