10061 토마토 Gold V

문제

N×M 크기의 창고에 토마토가 보관되어 있다. 1은 익은 토마토, 0은 안 익은 토마토, -1은 토마토가 없는 칸이다. 익은 토마토는 하루가 지나면 상하좌우 인접한 안 익은 토마토를 익게 한다.

모든 토마토가 익는 최소 일수를 구하는 프로그램을 작성하시오. 모두 이미 익어있으면 0, 모두 익지 못하면 -1을 출력한다.

입력

첫째 줄에 M (2 ≤ M ≤ 1,000)과 N (2 ≤ N ≤ 1,000)이 주어진다. 다음 N개의 줄에 창고의 상태가 주어진다.

출력

최소 일수를 출력한다.

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

8