벽 부수고 이동하기
면접 대비시간 제한2초메모리 제한192 MB
격자에서 벽을 최대 한 번 부술 수 있다는 조건 아래 좌상단에서 우하단까지 최단 경로 길이를 구합니다.
문제
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을 출력한다.