곰곰이의 식단 관리 2

$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)$ 에는 장애물이 없음이 보장된다.

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