Problem I
Gävlebocken 1
Du befinner dig i staden Gävle över jul. Du har därmed chansen i år att vara Sveriges hjälte - alltså att bränna ner Gävlebocken! Såklart vill du inte synas på en övervakningskamera när du gör detta - då blir du ju Sveriges syndabock istället (och tagen av polisen).
Du har skaffat dig en karta över området kring Gävlebocken. Kartan är helt rektangulär och för varje kvadratmeter visar den om det finns ett hus där (#), om platsen är synlig för en övervakningskamera (+) eller om det är fritt fram att gå där (.). På kartan finns också Gävlebocken (G) och rutan du börjar på (S) utmarkerade.
För varje steg du går kan du flytta dig till en annan ruta som delar en sida med den du är på (alltså upp, ner, vänster eller höger, inte diagonalt). Du får inte gå utanför kartan eller gå igenom hus.
Är det möjligt att ta dig till Gävlebocken utan att synas på kamera?
Indata
Första raden indata består av de två heltalen $R$ och $C$ ($2 \leq R \cdot C \leq 10^6$), hur många meter brett och långt området är som kartan täcker.
Därefter följer $R$ rader som var och en har $C$ tecken. Detta är kartan över Gävle. Det är garanterat att kartan har minst en rad och två kolumner, och att det finns exakt ett S och ett G på kartan.
Utdata
Skriv ut ”Ja :)” om du kan ta dig till Gävlebocken utan att synas på kamera eller ”Nej :(” om det inte är möjligt.
Poängsättning
Din lösning kommer att testas på flera olika testgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poäng |
Gränser |
|
$1$ |
$10$ |
$R = 1, C \leq 10^5$ |
|
$2$ |
$25$ |
$R = 2, C \leq 10^5$ |
|
$3$ |
$65$ |
Inga ytterligare begränsningar. |
| Exempel på indata 1 | Exempel på utdata 1 |
|---|---|
1 2 GS |
Ja :) |
| Exempel på indata 2 | Exempel på utdata 2 |
|---|---|
2 6 ##.... S..+.G |
Ja :) |
| Exempel på indata 3 | Exempel på utdata 3 |
|---|---|
2 3 S#G +++ |
Nej :( |
| Exempel på indata 4 | Exempel på utdata 4 |
|---|---|
10 10 S......... .......... .......... .......... ....G..... .......... .......... .......... .......... .......... |
Ja :) |
