시간 제한메모리 제한제출정답맞힌 사람정답 비율
3.5 초 1024 MB50616010929.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)$ 에는 장애물이 없음이 보장된다.

출력

곰곰이의 이동을 막기 위해 총총이가 추가로 놓아야 할 장애물의 최소 개수를 출력하라.

예제 입력 1

4 4
0 0 0 1
0 0 0 0
0 0 1 0
0 1 0 0

예제 출력 1

1

예제 입력 2

3 3
0 1 1
1 1 1
1 1 0

예제 출력 2

0

예제 입력 3

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

예제 출력 3

2

출처

Contest > BOJ User Contest > 곰곰컵 > 제2회 곰곰컵 I번