Fire Mountain

Interview

Time limit1sMemory limit1024 MB

Summary

In a grid where some cells are flames, find the shortest path from the top-left to the bottom-right cell while stepping on at most K flames.

Level: Medium6 of 10
Topics: BFS, Graph, Shortest path, Matrix
Solved: No attempts yet

Problem

On a trip to the fire mountains Yanar Dag in Azerbaijan (the host country of this year's International Programming Olympiad), you have gotten lost! The mountains have the shape of a grid with $R$ rows and $C$ columns. You are standing in the top-left corner of the grid and want to move to the tour bus in the bottom-right corner. Since the bus leaves soon, you want to get there as fast as possible. To reach the bus, you can move to a cell directly above, to the right of, below, or to the left of the one you are standing on.

However, on the fire mountains there are a number of flames, caused by natural gas seeping out of the mountains. Since you are wearing very fine clothes, you do not want to have to run through more flames than necessary. More precisely, you are prepared to walk through at most $K$ flames on your way to the bus.

Your task is to compute how fast you can move to the bus if you are allowed to walk through at most $K$ flames.

Input

The first line contains three integers $R$ ( $2 \le R \le 100$ ), $C$ ( $2 \le C \le 100$ ), and $K$ ( $0 \le K \le 200$ ). $R$ and $C$ are the number of rows and columns in the grid that makes up the fire mountains.

The following $R$ lines describe the fire mountains. The $i$ -th of these lines contains $C$ characters describing the $i$ -th row. Each character is either a dot (.) if a cell is empty or a hash (\#) if the cell contains a flame. The top-left cell and the bottom-right cell are always dots.

Output

Print an integer $N$ , the minimum number of steps you need to reach the bus. If you cannot reach the goal without walking through more than $K$ flames, print "nej".

Examples4

Example 1
Input
```
5 5 0
.....
#.#.#
..#.#
.#...
...#.
```
Expected output
```
8
```

Example 2

Input

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

Expected output

Example 3

Input

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

Expected output

nej

Example 4

Input

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

Expected output