/ 
実行時間制限: 1 sec / メモリ制限: 1024 MB
配点 : 300 点
問題文
縦 H 行、横 W 列の白黒に塗られたマス目が与えられます。
マス目の状態は A_{11} から A_{HW} の HW 個の文字で表されており、
上から i 行目、左から j 列目にあるマスが黒色のとき A_{ij} は #、
上から i 行目、左から j 列目にあるマスが白色のとき A_{ij} は . となっています。
すべてのマスが黒色になるまで、以下の操作を繰り返し行います。
- 辺を共有して隣接するマスの中に、黒色のマスが一つ以上存在するような白色のマスすべてが黒色になる。
何回の操作を行うことになるか求めてください。 ただし、最初に与えられるマス目には少なくとも 1 つ黒色のマスが存在します。
制約
- 1 ≦ H,W ≦ 1000
- A_{ij} は
#または. - 与えられるマス目には少なくとも 1 つ黒色のマスが存在する。
入力
入力は以下の形式で標準入力から与えられる。
H W
A_{11}A_{12}...A_{1W}
:
A_{H1}A_{H2}...A_{HW}
出力
行われる操作の回数を出力せよ。
入力例 1
3 3 ... .#. ...
出力例 1
2
操作を一回行うとマス目の四隅以外が黒色になり、もう一度操作を行うとすべてのマス目が黒色になります。
入力例 2
6 6 ..#..# ...... #..#.. ...... .#.... ....#.
出力例 2
3
Score : 300 points
Problem Statement
You are given a grid of squares with H horizontal rows and W vertical columns, where each square is painted white or black.
HW characters from A_{11} to A_{HW} represent the colors of the squares.
A_{ij} is # if the square at the i-th row from the top and the j-th column from the left is black, and A_{ij} is . if that square is white.
We will repeatedly perform the following operation until all the squares are black:
- Every white square that shares a side with a black square, becomes black.
Find the number of operations that will be performed. The initial grid has at least one black square.
Constraints
- 1 \leq H,W \leq 1000
- A_{ij} is
#or.. - The given grid has at least one black square.
Input
Input is given from Standard Input in the following format:
H W
A_{11}A_{12}...A_{1W}
:
A_{H1}A_{H2}...A_{HW}
Output
Print the number of operations that will be performed.
Sample Input 1
3 3 ... .#. ...
Sample Output 1
2
After one operation, all but the corners of the grid will be black. After one more operation, all the squares will be black.
Sample Input 2
6 6 ..#..# ...... #..#.. ...... .#.... ....#.
Sample Output 2
3