6123 : 치즈
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N×M 격자 판에 치즈(1)가 놓여 있습니다. 바깥 공기와 2면 이상 접촉하는 치즈는 1시간 만에 녹아 없어집니다.
단, 치즈 내부에 갇혀 있는 공기 구멍은 외부 공기와 직접 닿지 않으므로 치즈가 녹는 데 영향을 주지 않습니다. 치즈가 모두 녹는 데 걸리는 시간과, 다 녹기 1시간 전에 남아있던 치즈 조각(칸 수)을 구하시오.
단, 치즈 내부에 갇혀 있는 공기 구멍은 외부 공기와 직접 닿지 않으므로 치즈가 녹는 데 영향을 주지 않습니다. 치즈가 모두 녹는 데 걸리는 시간과, 다 녹기 1시간 전에 남아있던 치즈 조각(칸 수)을 구하시오.
입력 설명
첫째 줄에 세로 N, 가로 M (5 ≤ N, M ≤ 100)이 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 격자의 정보가 공백 구분되어 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 격자의 정보가 공백 구분되어 주어집니다.
출력 설명
첫째 줄에 치즈가 모두 녹아 없어지는 데 걸리는 시간(시간)을 출력하고, 둘째 줄에 완전히 다 녹기 1시간 전에 남아있는 치즈의 면적(칸 수)을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 5
0 0 0 0 0
0 1 1 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2
4도움
치즈가 녹는 판정을 내리기 전, 매 턴마다 (0,0)에서 시작하는 외부 공기 BFS 탐색을 하여 외부 공기와 접촉한 칸을 칠해두십시오. 이후 모든 치즈 칸을 돌며 인접한 외부 공기가 2면 이상인 치즈를 제거하십시오.