불의 산

면접 대비

시간 제한1초메모리 제한1024 MB

요약

일부 칸에 불꽃이 있는 격자에서 왼쪽 위에서 오른쪽 아래까지 최대 K개의 불꽃을 밟으며 이동하는 최단 경로의 길이를 구한다.

난이도: 보통10점 중 6점
유형: BFS, 그래프, 최단 경로, 행렬
정답자: 아직 제출이 없습니다

문제

아제르바이잔(올해 국제 프로그래밍 올림피아드가 열리는 나라)의 불의 산 Yanar Dag로 소풍을 갔다가 길을 잃었다! 산은 $R$ 개의 행과 $C$ 개의 열로 이루어진 격자 모양이다. 너는 격자의 왼쪽 위에 서 있고, 오른쪽 아래에 있는 소풍 버스로 이동하려고 한다. 버스가 곧 출발하기 때문에 최대한 빨리 가고 싶다. 버스로 가려면 지금 있는 칸의 위, 오른쪽, 아래, 왼쪽에 있는 칸으로 이동할 수 있다.

그런데 불의 산에는 산에서 새어 나오는 천연가스 때문에 생긴 불꽃이 여러 개 있다. 너는 아주 좋은 옷을 입고 있기 때문에 필요 이상으로 많은 불꽃을 뚫고 지나가고 싶지 않다. 더 정확히 말하면, 버스로 가는 길에 최대 $K$ 개의 불꽃을 지나갈 수 있다.

너의 임무는 최대 $K$ 개의 불꽃을 지나가면서 버스로 갈 수 있는 최소 이동 횟수를 구하는 것이다.

입력

첫 번째 줄에는 세 정수 $R$ ( $2 \le R \le 100$ ), $C$ ( $2 \le C \le 100$ ), $K$ ( $0 \le K \le 200$ )가 주어진다. $R$ 과 $C$ 는 불의 산을 이루는 격자의 행과 열의 수이다.

다음 $R$ 개의 줄은 불의 산의 모습을 나타낸다. 이 중 $i$ 번째 줄은 $i$ 번째 행의 모습을 나타내는 $C$ 개의 문자로 이루어져 있다. 각 문자는 칸이 비어 있으면 점(.), 칸에 불꽃이 있으면 샵(\#)이다. 왼쪽 위 칸과 오른쪽 아래 칸은 항상 점이다.

출력

버스로 가는 데 필요한 최소 이동 횟수 $N$ 을 정수로 출력한다. $K$ 개를 초과하는 불꽃을 지나지 않고는 목표에 도달할 수 없다면 "nej"를 출력한다.

예제4

예제 1
입력
```
5 5 0
.....
#.#.#
..#.#
.#...
...#.
```
예상 출력
```
8
```

예제 2

입력

6 6 1
.##...
.##.#.
.##.#.
.#..#.
.#.##.
...##.

예상 출력

예제 3

입력

6 6 1
.##...
.##.#.
.##.#.
##..##
.#.##.
...##.

예상 출력

nej

예제 4

입력

6 6 0
.###.#
.#.#.#
.#....
...##.
#.###.
#####.

예상 출력