JOI 군은 가족과 함께 해수욕을 왔다. 실컷 헤엄쳐 지친 JOI 군은 이번에는 모래사장에서 모래성을 만들어 놀았다. 잠시 뒤 모래놀이도 질리자, 성을 그대로 두고 다시 바다로 헤엄치러 갔다. JOI 군이 만든 성은 모래사장의 어떤 직사각형 영역에 들어 있다. 이 직사각형은 동서남북으로 칸이 나뉘어 있다. 각 칸은 JOI 군이 만든 성의 일부인 칸(이하 「성 칸」)이거나 그렇지 않은 칸(이하 「빈 칸」)이다. 각 성 칸에는 「강도」라 부르는 \(1\) 이상 \(9\) 이하의 정수가 정해져 있다. 직사각형의 가장자리, 곧 바깥과 맞닿은 칸에는 성 칸이 없다. 이윽고 밀물이 와서 직사각형 영역에도 파도가 밀려온다. 파도가 \(1\)번 밀려올 때마다, 성 칸 가운데 다음 조건을 만족하는 것은 모두 한꺼번에 무너져 빈 칸이 된다. 조건: 둘레 \(8\)칸(동서남북 및 북동, 북서, 남동, 남서 방향으로 이웃한 칸)에 있는 빈 칸의 수가 그 칸의 강도 이상이다. 파도가 빠지면 곧 다음 파도가 밀려온다. 파도가 충분히 많이 밀려오면 성이 모두 무너지거나, 튼튼한 부분만 남아 파도가 밀려와도 성 칸이 하나도 무너지지 않는 상태에 이른다. 성 칸을 \(1\)개 이상 무너뜨리는 파도가 밀려오는 횟수를 구하라. |
입력은 다음 형식으로 주어진다.
\(H\) \(W\)
\(S_1\)
\(S_2\)
\(\vdots\)
\(S_H\)
- 입력은 \(1+H\)줄이다.
- 첫째 줄에 정수 \(H\), \(W\)가 공백 하나로 구분되어 주어진다. 직사각형이 세로 \(H\)행, 가로 \(W\)열의 \(H \times W\)칸으로 나뉘어 있음을 나타낸다. 세로는 남북, 가로는 동서이다.
- 이어지는 \(H\)줄에 각각 길이 \(W\)의 문자열이 공백 없이 주어지고, 첫 파도가 오기 전 상태를 나타낸다. \(i\)번째 줄의 왼쪽에서 \(j\)번째 문자(\(1 \le i \le H\), \(1 \le j \le W\))는 북쪽에서 \(i\)행, 서쪽에서 \(j\)열의 칸이 빈 칸이면 . 이다. 성 칸이면 \(1, 2, \ldots, 9\) 중 하나이고 그 칸의 강도를 나타낸다.
- 직사각형의 가장자리는 모두 빈 칸이다. 곧 모든 입력에서 \(1\)번째 줄 또는 \(H\)번째 줄의 문자와, 각 줄의 왼쪽에서 \(1\)번째 또는 \(W\)번째 문자는 모두 . 이다.
- \(2 \le H \le 1000\)
- \(2 \le W \le 1000\)
- 채점용 입력 \(1\)에서는 \(H \le 50\), \(W \le 50\)을 만족한다.
다음 형식으로 출력한다.
첫째 줄에 성 칸을 \(1\)개 이상 무너뜨리는 파도가 밀려오는 횟수를 출력한다.
처음 파도에 강도 \(3\)의 성 칸이 모두 무너지고, 다음 파도에 강도 \(2\), 그다음 파도에 강도 \(4\)의 성 칸이 무너진다. 이후 파도는 성 칸을 무너뜨리지 않는다. 따라서 답은 \(3\)이다.