빙산

지구 온난화로 북극의 빙산이 녹고 있다. 빙산의 높이를 N x M 2차원 배열로 나타낸다. 빙산이 있는 칸에는 양의 정수 높이가 저장되고, 바다인 칸에는 0이 저장된다. 빈칸은 모두 0이라고 생각한다.

그림 1. 5행 7열 배열에 저장된 빙산의 높이

빙산은 바다와 많이 닿을수록 더 빨리 녹는다. 매년 빙산 칸의 높이는 동서남북 네 방향으로 인접한 0 칸의 개수만큼 줄어든다. 단, 높이는 0보다 작아지지 않는다. 빙산에 둘러싸여 호수처럼 보이는 0 칸도 바다로 간주한다. 모든 칸의 감소량은 그 해가 시작될 때의 배열을 기준으로 동시에 계산한다. 그림 1의 빙산은 1년 뒤 그림 2처럼 변한다.

그림 2

그림 3은 그림 1의 빙산이 2년 뒤 변한 모습이다. 2차원 배열에서 동서남북으로 인접한 빙산 칸들은 서로 연결되어 있다고 한다. 그림 2의 빙산은 한 덩어리이지만, 그림 3의 빙산은 세 덩어리로 분리되어 있다.

그림 3

처음에는 하나의 덩어리인 빙산이 주어진다. 이 빙산이 처음으로 두 덩어리 이상으로 분리되는 데 걸리는 시간(년)을 구하라. 그림 1의 경우 답은 2이다. 끝까지 녹는 동안 두 덩어리 이상으로 분리되지 않으면 0을 출력한다.

첫 줄에 행의 개수 N과 열의 개수 M이 공백으로 구분되어 주어진다. N과 M은 각각 3 이상 300 이하이다.

다음 N개의 줄에는 각 행의 M개 정수가 공백으로 구분되어 주어진다. 각 값은 0 이상 10 이하이다. 높이가 1 이상인 빙산 칸의 수는 10,000개 이하이다. 첫 번째 행과 마지막 행, 첫 번째 열과 마지막 열은 항상 0이다.

빙산이 처음으로 두 덩어리 이상으로 분리되는 시간(년)을 첫 줄에 출력한다. 빙산이 모두 녹을 때까지 분리되지 않으면 0을 출력한다.