1290: 조각난 미로(Fragmented Labyrinth)

N x M 크기의 격자 형태의 미로가 있습니다. 이 미로는 '조각'들로 이루어져 있으며, 각 조각은 1x1 크기의 칸에 해당합니다.

어떤 조각은 벽('#')이라서 지나갈 수 없고, 어떤 조각은 길('.')이라서 지나갈 수 있습니다.

당신은 이 미로의 특정 지점(R, C)에서 출발하여, 미로의 네 가장자리 중 한 곳에 도달하면 탈출하는 것으로 간주합니다.

즉, 행이 1 또는 N이거나, 열이 1 또는 M인 길 칸에 도착하면 탈출입니다.

그런데 이 미로에는 특별한 규칙이 있습니다.

바로 **'망치'**를 K개 가지고 출발한다는 점입니다.

당신은 길을 가다가 벽을 만나면, 망치를 사용하여 그 벽을 길로 바꿀 수 있습니다.

벽 하나를 부수는 데는 망치 하나가 소모되며, 한 번 길로 바뀐 벽은 다시 벽이 되지 않습니다.

당신의 목표는 출발 지점에서 미로의 가장자리까지 도달하는 데 필요한 최소 시간을 구하는 것입니다.

단, 망치는 모두 소진해야 합니다.

상하좌우 인접한 칸으로 한 칸 이동하는 데는 1의 시간이 걸립니다.

벽을 부수는 데에는 추가 시간이 걸리지 않습니다. 만약 탈출이 불가능하다면 -1을 출력합니다.

첫째 줄에 미로의 세로 크기 N과 가로 크기 M, 그리고 망치의 개수 K가 공백으로 구분되어 주어집니다. (1 ≤ N, M ≤ 1,000, 0 ≤ K ≤ 10)

둘째 줄에 출발 지점의 좌표 R, C가 공백으로 구분되어 주어집니다. (1 ≤ R ≤ N, 1 ≤ C ≤ M)

셋째 줄부터 N개의 줄에 걸쳐 미로의 정보가 주어집니다. '.'은 길, '#'은 벽을 의미합니다. 출발 지점 (R, C)은 항상 길('.')입니다.

출발 지점에서 미로의 가장자리까지 도달하는 데 걸리는 최소 시간을 출력합니다. 만약 탈출이 불가능하다면 -1을 출력합니다.

5 5 0
3 3
.....
.###.
.#.#.
.###.
.....

-1