벽 부수고 이동하기

N × M 크기의 격자 지도가 주어진다. 지도에서 0은 이동할 수 있는 칸, 1은 이동할 수 없는 벽을 뜻한다.

(1, 1)에서 출발해 (N, M)까지 이동하려고 한다. 경로의 길이는 지나가는 칸의 개수이며, 시작 칸과 도착 칸도 모두 포함해서 센다.

이동하는 동안 벽을 하나 부수면 도착할 수 있거나 경로가 더 짧아질 수 있다면, 벽을 최대 한 개까지 부수고 이동할 수 있다.

한 칸에서는 상하좌우로 인접한 칸으로 이동할 수 있다.

지도가 주어졌을 때 가능한 최단 경로의 길이를 구하는 프로그램을 작성하시오.

첫째 줄에 N과 M이 주어진다 (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 1,000).

다음 N개의 줄에는 각각 M개의 숫자로 지도가 주어진다.

(1, 1)과 (N, M)은 항상 0이다.

최단 경로의 길이를 출력한다. 도착할 수 없으면 -1을 출력한다.