Minigolf

Interview

Time limit4sMemory limit1024 MB

Summary

On a grid with walls, a ball can be putted 1 to K cells in a straight line; find the fewest putts to reach the hole.

Level: Medium6 of 10
Topics: BFS, Graph, Array, Implementation
Solved: No attempts yet

Problem

You are playing minigolf on an $R\times C$ grid. In one stroke you can putt the ball any number of steps up to $K$ straight in one of the four directions: up, down, right, left. You cannot putt the ball through a wall or off the course, of course.

Your task is to compute the minimum number of putts needed to get the ball into the hole.

Input

The first line contains three integers $R$ , $C$ and $K$ ( $1 \le R\times C \le 1\,000\,000$ and $1\le K \le 1\,000\,000$ ): the number of rows, the number of columns, and how far you can putt.

Then follow $R$ lines, each with $C$ characters, describing the minigolf course:

"." means the cell is empty.
"#" means the cell contains a wall.
"S" means this cell is the one you start from. There is exactly one "S" in the input.
"G" means this cell contains the hole. There is exactly one "G" in the input.

It is guaranteed that the hole can be reached from the starting cell.

Output

Print one integer: the minimum number of putts you need to shoot the ball into the hole.

Examples3

Example 1
Input
```
2 3 2
S.G
...
```
Expected output
```
1
```
Example 2
Input
```
2 5 1
S#...
...#G
```
Expected output
```
7
```

Example 3

Input

16 10 100
..######..
.#......#.
#...G....#
#........#
.#......#.
..#....#..
..#....#..
..###..#..
..#....#..
..#..###..
..#....#..
..###..#..
..#....#..
..#....#..
..#.S..#..
..######..

Expected output