골드 V설명
\(N \times M\) 격자 창고에 토마토가 보관되어 있다. 익은 토마토는 \(1\), 익지 않은 토마토는 \(0\), 토마토가 없는 칸은 \(-1\)이다.
하루가 지나면 익은 토마토의 상하좌우에 있는 익지 않은 토마토가 익는다. 모든 토마토가 익을 때까지 걸리는 최소 일수를 구하여라. 저장될 때부터 모두 익어 있으면 \(0\)을, 끝내 모두 익지 못하면 \(-1\)을 출력한다.
제약
\(2 \le N \times M\), \(1 \le N, M \le 1\,000\).
입력 형식
첫째 줄에 가로 칸 수 \(M\)과 세로 칸 수 \(N\)이 주어진다. 다음 \(N\)개의 줄에 각 행의 정보가 \(M\)개의 정수(\(1\), \(0\), \(-1\))로 주어진다. 토마토는 하나 이상 있다.
출력 형식
모든 토마토가 익는 최소 일수를 출력한다. 불가능하면 \(-1\).
예제 1
입력
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
설명
맨 구석의 토마토 하나에서 퍼져 \(8\)일이 걸린다.
예제 2
입력
6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1
출력
6
설명
벽(\(-1\))을 돌아서 익는다.
힌트
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
힌트 1
로그인하고 잠금 해제 · 25 🪙
힌트 2
로그인하고 잠금 해제 · 50 🪙
문제 정보
riseoj 작성
출처 Original
태그