Minigolf

문제

Du spelar minigolf på ett $R\times CR\backslash times\; C$ rutnät. På ett slag kan du putta golfbollen valfritt antal steg upp till $KK$ rakt i en av de fyra riktningarna upp, ner, höger, vänster. Du kan såklart inte putta bollen igenom en vägg eller utanför banan.

Din uppgift är att beräkna det minsta antalet puttar som behövs för att få ner bollen i hålet.

입력

Den första raden innehåller tre heltal $RR$, $CC$ och $KK$ ($1\le R\times C\le 10000001\; \backslash le\; R\backslash times\; C\; \backslash le\; 1\backslash ,000\backslash ,000$ och $1\le K\le 10000001\backslash le\; K\; \backslash le\; 1\backslash ,000\backslash ,000$) -- antal rader, antalet kolumner och hur långt du kan putta.

Därefter följer $RR$ rader, vardera med $CC$ tecken, som beskriver minigolfbanan:

• "." betyder att rutan är tom.
• "#" betyder att rutan har en vägg i sig.
• "S" betyder att denna rutan är den du startar från. Det kommer finnas exakt ett "S" i indatan.
• "G" betyder att denna rutan är den med hålet i. Det kommer finnas exakt ett "G" i indatan.

Det är garanterat att det är möjligt att nå hålet från startrutan.

출력

Skriv ut ett heltal -- det minsta antalet puttar du behöver för att skjuta bollen i hålet.

2 3 2
S.G
...

1

2 5 1
S#...
...#G

7

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

7