Light Road#3286
You are given an N \times M grid (2 \leq N, M \leq 100). There is an evil creature in one of the grid squares, and a laser generator is located in a different square. The generator always shoots a laser beam to the south. Since the position and orientation of the generator are fixed, you may have to use several mirrors to reflect the beam towards the creature. There are some obstacles on the grid, and you have a limited number of mirrors. Determine if you can kill the creature, and if so, find the minimum number of mirrors needed.
There are two types of single-sided mirrors:
Type : can be placed at 45^\circ or 225^\circ from the east-west direction.
Type : can be placed at 135^\circ or 315^\circ from the east-west direction.
For example, if four mirrors are positioned properly, the laser shoots as shown below:
You have type mirrors and type mirrors (0 \leq A \leq 10). Note that mirrors are single-sided, so the back side (shown with a cross in the figure above) does not reflect. You cannot place mirrors on the squares containing the creature or the laser generator, although the laser beam can pass through those squares. The creature is killed if the laser can reach the square it occupies.
The first line contains three integers , , and (2 \leq N, M \leq 100, 0 \leq A \leq 10). Each of the next lines contains characters, describing the grid:
# : obstacle
. : empty square
S : laser generator (unique)
G : evil creature (unique)
The first line describes the northernmost row, the last line the southernmost. There is exactly one laser generator and one creature, and the generator always emits its beam to the south.
Print the minimum number of mirrors required to kill the creature, or -1 if it is impossible.
Örnek 1