0207 - 砂の城 (Sandcastle)

問題

JOI 君は家族とともに海水浴に来た．さんざん泳いで泳ぎ疲れた JOI 君は，次は砂浜で砂の城を作って遊んだ．しばらくして砂遊びにも飽きると，JOI 君は城を放置してまた海に泳ぎに向かった．

JOI 君が作った城は，砂浜のうちのある長方形の領域に含まれている．この長方形の領域は，東西南北にマス目状に区切られている．各マスは，JOI 君が作った城の一部であるマス (以下，「城マス」と呼ぶ) かそうでないマス (以下，「更地マス」と呼ぶ) のいずれかである．それぞれの城マスには「強度」と呼ばれる 1 以上 9 以下の整数が定まっている．長方形の領域の外縁部，すなわち外側と接しているマスには城マスは存在しない．

やがて潮が満ちてきて，長方形の領域にも波が押し寄せてくるようになった．波が 1 つ押し寄せてくるたびに，城マスのうち次の条件を満たすものはすべて一斉に崩壊して，更地マスに変化する．

• 条件： 周囲の 8 マス (東西南北および北東，北西，南東，南西方向に隣接するマス) にある更地マスの数が，そのマスの強度の値以上である．

波が引くと，まもなく次の波が押し寄せて来る．

十分多くの波が押し寄せると，城がすべて崩れてしまうか，丈夫な部分だけが残るかして，波が押し寄せてきても 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 行で出力せよ．

入出力例

入力例 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