Informatica Online Judge

  백신 프로그램 [0888 / 0378]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 45   Total Tried : 56


The Champion of this Problem (C++) : gs19022 - 0ms / 660byte
My Best Submission (C++) : N/A

[]

Background

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

아래 <그림>에서 하얀색 부분은 치료가 완료된 부분이고 그렇지 않은 부분은 아직 바이러스에 감염되어 있는 부분이다. 이 바이러스를 치료하는 데 있어 바이러스의 4면 중 2면 이상이 치료된 부분과 접하면 1초 후에 치료가 가능하다.

<그림>과 같이 바이러스가 감염되어 있다면 V로 표시된 부분의 바이러스 격자는 1초 후에 치료가 되어 흰색으로 변한다. 그리고 그 안쪽에 있던 바이러스들도 2면 이상이 치료된 부분과 접촉되면 1초 후에 치료가 될 것이다.

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

Input

1. 첫째 줄에는 행과 열의 수를 나타내는 두 개의 정수 n, m이 주어진다.
2. 둘째 줄부터 n +1줄 까지는 메모리에 바이러스가 있는 부분은 1로 표시되고, 바이러스가 치료된 부분은 0으로 표시된다.
3. 각 0과 1은 하나의 공백으로 분리되어 있다.

[입력값의 정의역]
5 ≦ n ≦ 100, 5 ≦ m ≦ 100

Output

첫 줄에는 주어진 바이러스가 모두 치료되는데 걸리는 최소 시간(초)을 정수로 출력한다.

IO Example

입력
8 9
0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 1 1 0
0 0 0 1 1 0 1 1 0
0 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 0
0 1 1 1 0 1 1 0 0
0 1 1 0 0 1 1 0 0
0 0 0 0 0 0 0 0 0

출력
5

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]