1494: 3538: 백신 프로그램

모눈종이 모양의 컴퓨터 메모리가 있다. n은 행의 수이고 m은 열의 수이다. 이 메모리 공간에 바이러스가 감염되어 백신 프로그램으로 치료를 하려고 한다.

아래 <그림>에서 하얀색 부분은 치료가 완료된 부분이고 그렇지 않은 부분은 아직 바이러스에 감염되어 있는 부분이다. 이 바이러스를 치료하는 데 있어 바이러스의 4면 중 2면 이상이 치료된 부분과 접하면 1초 후에 치료가 가능하다. <그림>과 같이 바이러스가 감염되어 있다면 V로 표시된 부분의 바이러스 격자는 1초 후에 치료가 되어 흰색으로 변한다. 그리고 그 안쪽에 있던 바이러스들도 2면 이상이 치료된 부분과 접촉되면 1초 후에 치료가 될 것이다.

메모리의 맨 가장자리에는 바이러스가 감염될 수 없는 영역으로 가정한다. 입력으로 주어진 바이러스가 모두 치료되는데 걸리는 최소 시간을 구하는 프로그램을 작성하시오.

<그림>

1. 첫째 줄에는 행과 열의 수를 나타내는 두 개의 정수 n, m이 주어진다.

(단, 5 ≦ n ≦ 100, 5 ≦ m ≦ 100)

2. 둘째 줄부터 n +1줄 까지는 메모리에 바이러스가 있는 부분은 1로 표시되고, 바이러스가 치료된 부분은 0으로 표시된다.

3. 각 0과 1은 하나의 공백으로 분리되어 있다