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 |
