配点 : $300$ 点

問題文

縦 $H$ 行、横 $W$ 列の白黒に塗られたマス目が与えられます。 マス目の状態は $A_{11}$ から $A_{HW}$ の $HW$ 個の文字で表されており、 上から $i$ 行目、左から $j$ 列目にあるマスが黒色のとき $A_{ij}$ は #、 上から $i$ 行目、左から $j$ 列目にあるマスが白色のとき $A_{ij}$ は . となっています。

すべてのマスが黒色になるまで、以下の操作を繰り返し行います。

• 辺を共有して隣接するマスの中に、黒色のマスが一つ以上存在するような白色のマスすべてが黒色になる。

何回の操作を行うことになるか求めてください。 ただし、最初に与えられるマス目には少なくとも $1$ つ黒色のマスが存在します。

制約

• $1 \leq H,W \leq 1000$
• $A_{ij}$ は # または .
• 与えられるマス目には少なくとも $1$ つ黒色のマスが存在する。

入力

入力は以下の形式で標準入力から与えられる。

$H$ $W$

$A_{11}$$A_{12}$$...$$A_{1W}$

$:$

$A_{H1}$$A_{H2}$$...$$A_{HW}$

出力

行われる操作の回数を出力せよ。

3 3
...
.#.
...

2

操作を一回行うとマス目の四隅以外が黒色になり、もう一度操作を行うとすべてのマス目が黒色になります。

6 6
..#..#
......
#..#..
......
.#....
....#.

3