모래성

문제

JOI 군은 가족과 함께 해수욕을 하러 왔다. 실컷 헤엄쳐서 헤엄치기에 지친 JOI 군은, 다음으로 모래사장에서 모래성을 만들며 놀았다. 얼마 후 모래놀이에도 싫증이 나자, JOI 군은 성을 내버려 두고 다시 바다로 헤엄치러 갔다.

JOI 군이 만든 성은 모래사장 중 어떤 직사각형 영역에 포함되어 있다. 이 직사각형 영역은 동서남북으로 격자 모양으로 나뉘어 있다. 각 칸은 JOI 군이 만든 성의 일부인 칸 (이하 「성 칸」이라고 부른다) 이거나 그렇지 않은 칸 (이하 「빈터 칸」이라고 부른다) 중 하나이다. 각 성 칸에는 「강도」라고 불리는 1 이상 9 이하의 정수가 정해져 있다. 직사각형 영역의 가장자리, 즉 바깥쪽과 접해 있는 칸에는 성 칸이 존재하지 않는다.

이윽고 밀물이 들어와 직사각형 영역에도 파도가 밀려오게 되었다. 파도가 1 번 밀려올 때마다, 성 칸 중 다음 조건을 만족하는 것은 모두 일제히 붕괴하여 빈터 칸으로 변한다.

• 조건： 주위의 8 칸 (동서남북 및 북동, 북서, 남동, 남서 방향으로 인접한 칸) 에 있는 빈터 칸의 수가 그 칸의 강도의 값 이상이다.

파도가 물러가면 머지않아 다음 파도가 밀려온다.

충분히 많은 파도가 밀려오면, 성이 전부 무너져 버리거나 튼튼한 부분만 남거나 하여, 파도가 밀려와도 성 칸이 하나도 붕괴하지 않는 상태로 안정된다. 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