벽 부수고 이동하기 3
면접 대비시간 제한2초메모리 제한512 MB
격자에서 왼쪽 위에서 오른쪽 아래로 가는 최단 경로를 찾는다. 낮에만 벽을 최대 K개 부술 수 있고 이동하거나 제자리에 머무를 때마다 낮과 밤이 바뀐다.
문제
N×M 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳, 1은 이동할 수 없는 벽이 있는 곳이다. (1, 1)에서 (N, M)까지 최단 경로로 이동하려 한다. 최단 경로란 맵에서 지나는 칸의 개수가 가장 적은 경로이며, 시작 칸과 끝 칸도 포함해서 센다. 이동하지 않고 같은 칸에 머무르는 것도 가능하다. 이때도 방문한 칸의 개수가 하나 늘어난 것으로 본다.
이번 문제에서는 낮과 밤이 번갈아 나타난다. 처음 이동할 때는 낮이고, 이동할 때마다 낮과 밤이 바뀐다. 이동하지 않고 같은 칸에 머무르는 경우에도 낮과 밤이 바뀐다.
이동하는 도중에 벽을 부수고 가는 편이 경로를 더 짧게 만든다면, 벽을 K개까지 부수고 이동해도 된다. 단, 벽은 낮에만 부술 수 있다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
맵이 주어졌을 때 최단 경로를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)가 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정한다.
출력
첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.