지구 온난화로 인하여 북극의 빙산이 녹고 있습니다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 합시다. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장됩니다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장됩니다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각합니다.
0 0 0 0 0 0 0
0 2 4 5 3 0 0
0 3 0 2 5 2 0
0 7 6 2 4 0 0
0 0 0 0 0 0 0
그림 1. 행의 개수가 5이고 열의 개수가 7인 2차원 배열에 저장된 빙산의 높이 정보
빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어듭니다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않습니다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있습니다. 따라서 그림 1의 빙산은 일년 후에 다음과 같이 변형됩니다.
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 4 1 0 0 0 0 0 3 0 0 0 0 1 0 1 5 0 0 0 0 0 0 4 0 0 0 5 4 1 2 0 0 0 3 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (그림2) (그림3)
한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답입니다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력합니다.
그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어집니다. 각 칸에 들어가는 값은 0 이상 10 이하이고, 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000개 이하입니다.
배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워집니다.
입력 5 7 0 0 0 0 0 0 0 0 2 4 5 3 0 0 0 3 0 2 5 2 0 0 7 6 2 4 0 0 0 0 0 0 0 0 0 출력 2
출처:제23회한국정보올림피아드(2006.7.14) 초등부 문제 2