時間制限:$2.0sec$ / メモリ制限:$256MB$
JOI 君は家族とともに海水浴に来た．さんざん泳いで泳ぎ疲れた JOI 君は，次は砂浜で砂の城を作って遊んだ．しばらくして砂遊びにも飽きると，JOI 君は城を放置してまた海に泳ぎに向かった．
JOI 君が作った城は，砂浜のうちのある長方形の領域に含まれている．この長方形の領域は，東西南北にマス目状に区切られている．各マスは，JOI 君が作った城の一部であるマス (以下，「城マス」と呼ぶ) かそうでないマス (以下，「更地マス」と呼ぶ) のいずれかである．それぞれの城マスには「強度」と呼ばれる 1 以上 9 以下の整数が定まっている．長方形の領域の外縁部，すなわち外側と接しているマスには城マスは存在しない．
やがて潮が満ちてきて，長方形の領域にも波が押し寄せてくるようになった．波が 1 つ押し寄せてくるたびに，城マスのうち次の条件を満たすものはすべて一斉に崩壊して，更地マスに変化する．
波が引くと，まもなく次の波が押し寄せて来る．
十分多くの波が押し寄せると，城がすべて崩れてしまうか，丈夫な部分だけが残るかして，波が押し寄せてきても 1 つも城マスが崩壊しないような状態に落ち着く．1 つ以上の城マスを崩壊させるような波が押し寄せてくる回数を求めよ．
入力は 1 + H 行からなる．
1 行目には，2 つの整数 H, W (2 ≦ H ≦ 1000, 2 ≦ W ≦ 1000) が空白を区切りとして書かれている．これは，長方形の領域が縦 H 行，横 W 列の H × W 個のマスに区切られていることを表す．長方形の縦方向は南北方向であり，横方向は東西方向である．
続く H 行にはそれぞれ W 文字からなる文字列が書かれており，最初の波が押し寄せてくる前の長方形の領域の状態を表す．H 行のうちの i 行目の左から j 番目の文字 (1 ≦ i ≦ H, 1 ≦ j ≦ W) は，長方形の領域の北から i 行目，西から j 列目のマスが更地マスである場合は '.' (ピリオド) である．城マスである場合は '1', '2', ..., '9' のいずれかであり，そのマスの強度を表す．
長方形の領域の外縁部はすべて更地マスである．すなわち，すべての入力において，1 行目または H 行目の文字と，各行の左から 1 番目または W 番目の文字はすべて '.' である．
与えられる入力データのうち，入力 1 では H ≦ 50, W ≦ 50 を満たす．
1 つ以上の城マスを崩壊させるような波が押し寄せてくる回数を 1 行で出力せよ．
5 6
......
.939..
.3428.
.9393.
......
3
入出力例 1 においては，初めに押し寄せる波で強度 3 の城マスがすべて崩壊し，
...... .9.9.. ..428. .9.9.. ......
という状態になる．
次に押し寄せてくる波では強度 2 の城マスが崩壊し，
...... .9.9.. ..4.8. .9.9.. ......
という状態になる．
次に押し寄せてくる波では強度 4 の城マスが崩壊し，
...... .9.9.. ....8. .9.9.. ......
という状態になる．
これ以降の波が城マスを崩すことはない．よって答えは 3 である．
10 10
..........
.99999999.
.9.323239.
.91444449.
.91444449.
.91444449.
.91444449.
.91232329.
.99999999.
..........
35
部分点解法
すべてのマスを調べて崩れるかどうか判定する，という動作を繰り返す．崩れる城マスが一つも無くなったら終了．
計算量は $O( (答え) × HW)$ となる．サンプル入力２を見ればわかるとおり，答えは $HW$ 程度の大きさになりうる．そのため計算量は $O(H^2W^2)$ となり，入力１では間に合うが，入力２以降は現実的な時間内に計算が終わらない．
満点解法
次の事実に注目しよう．二回目以降の波においては，崩れる城マスの候補は，前回の波で崩れたマスの周囲８マスにあるものに限られる．そのため，そのようなマスについてのみ崩れるかどうか判定すればよい．
このような方針で計算すると，任意の城マスについて，それが崩れるかどうかの判定は高々８回しか行われないことになる．そのため計算量は $O(HW)$ となり，すべての入力に対して現実的な時間内に計算が終了する．
実装では，各波に対して，それによって崩れる城マスの位置をキューやスタックといったデータ構造に格納して記録すればよい．直前のひとつの波についてのみ記録しておけばよいので，次のようにすれば，用いるキューは実は二つで足りる．
また，各マスについて，周囲の更地マスの数を記録し，あるマスが崩壊するたびに更新していくようにすれば，崩れるかどうかの判定が楽になる．