시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3.5 초 | 1024 MB | 506 | 160 | 109 | 29.380% |
$N$행 $M$열 크기의 격자판이 있고, 이 격자판의 $(N,M)$ 위치에는 맛있는 치킨이 놓여 있다. 곰곰이는 $(1,1)$ 에서 출발하여 치킨을 향해 이동하려 한다. 곰곰이는 상하좌우 방향으로 자유롭게 이동할 수 있지만, 장애물이 있는 칸으로 이동하거나 격자판 바깥으로 나갈 수는 없다.
곰곰이의 헬스 트레이너인 총총이는 곰곰이가 치킨으로 이동하는 것을 막기로 했다. 총총이는 현재 장애물이 없는 칸에 장애물을 새로 놓아 곰곰이의 이동을 방해할 수 있다. 만약 격자판에 벌써 장애물이 놓여 있는 칸이 있다면, 총총이는 새로 장애물을 놓는 횟수를 절약할 수 있을지도 모른다.
격자판의 상태가 주어졌을 때, 총총이가 곰곰이의 이동을 막기 위해 추가로 놓아야 할 장애물의 최소 개수를 출력하라. $(1, 1)$ 과 $(N, M)$ 에는 장애물을 놓을 수 없다.
첫째 줄에 정수 $N, M$이 공백을 사이에 두고 주어진다. ($1 \le N, M \le 2\ 000$, $3 \le N \times M$)
둘째 줄부터 $N$개의 줄에 걸쳐 격자판의 상태가 주어진다. $0$이면 지나갈 수 있는 칸, $1$이면 장애물이 있어 지나갈 수 없는 칸을 뜻한다.
$(1,1)$ 과 $(N,M)$ 에는 장애물이 없음이 보장된다.
곰곰이의 이동을 막기 위해 총총이가 추가로 놓아야 할 장애물의 최소 개수를 출력하라.
4 4 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0
1
3 3 0 1 1 1 1 1 1 1 0
0
9 10 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0
2
Contest > BOJ User Contest > 곰곰컵 > 제2회 곰곰컵 I번