Hide

Problem D
Minigolf

Du spelar minigolf på ett $R\times C$ rutnät. På ett slag kan du putta golfbollen valfritt antal steg upp till $K$ 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.

Indata

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

Därefter följer $R$ rader, vardera med $C$ 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.

Utdata

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

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Grupp

Poängvärde

Gränser

$1$

$8$

Det finns inga väggar (“#”) i indatan

$2$

$18$

$R = 2$

$3$

$22$

$1\le R,C,K\le 100$

$4$

$25$

$K \ge \text {max}(R,C)$, dvs du är inte begränsad av hur långt du kan putta

$5$

$27$

Inga ytterligare begränsningar

Notera att vissa exemplelfall är inte giltiga i vissa testfallsgrupper.

Exempelfall

Sample Input 1 Sample Output 1
2 3 2
S.G
...
1
Sample Input 2 Sample Output 2
2 5 1
S#...
...#G
7
Sample Input 3 Sample Output 3
16 10 100
..######..
.#......#.
#...G....#
#........#
.#......#.
..#....#..
..#....#..
..###..#..
..#....#..
..#..###..
..#....#..
..###..#..
..#....#..
..#....#..
..#.S..#..
..######..
7

Please log in to submit a solution to this problem

Log in