골드 V설명
창고에 토마토가 \(N \times M\) 격자 상자에 담겨 있다. 각 칸의 값은 익은 토마토(1), 익지 않은 토마토(0), 토마토가 없는 칸(-1)을 의미한다.
하루가 지나면 익은 토마토와 상하좌우로 인접한 익지 않은 토마토가 익는다.
모든 토마토가 익을 때까지 걸리는 최소 일수를 구하여라. 처음부터 모두 익어 있으면 \(0\)을, 끝내 모두 익지 못하면 \(-1\)을 출력한다.
제약
- \(1 \le N, M \le 1\,000\)
입력 형식
첫째 줄에 \(N\)과 \(M\)이 주어진다.
다음 \(N\)개의 줄에 각각 \(M\)개의 정수가 공백으로 주어진다. 각 값은 \(-1\), \(0\), \(1\) 중 하나이다.
출력 형식
최소 일수, 또는 불가능하면 \(-1\)을 출력한다.
예제 1
입력
3 3
0 0 0
0 1 0
0 0 0출력
2설명
가운데서 시작해 바깥으로 퍼지므로 모서리까지 2일 걸린다.
예제 2
입력
2 2
1 0
0 -1출력
1설명
익은 토마토 옆 두 칸이 1일 만에 모두 익는다.
힌트
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
힌트 1
로그인하고 잠금 해제 · 10 🪙
힌트 2
로그인하고 잠금 해제 · 20 🪙
문제 정보
riseoj 작성
출처 Original
태그
