토마토
골드 V의견: 0
\(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\).
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\)일이 걸린다.
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\))을 돌아서 익는다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
토마토
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
토마토