Skridskor
Natalie har köpt nya skridskor, och har bestämt sig för att prova dem vid sin lokala skridskobana. Skridskobanan är formad som en rektangel, och på banan står ett antal hinder utplacerade. Natalie befinner sig på västra sidan av rinken, och vill nu ta sig över till andra sidan (den östra).
Natalie är ganska dålig på att åka skridskor. När Natalie åker in på isen genom ingången så kan hon inte svänga förrän hon stöter på ett hinder. När hon stöter på det första hindret så kan hon välja att svänga vänster eller höger, för att sedan fortsätta rakt fram, och så vidare. Hon svänger alltså alltid 90 grader vänster eller höger när hon stött på ett hinder – och hon kan enbart svänga när hon stött på ett hinder.
Natalie vill göra turen så enkel som möjligt. Vad är det minsta antal svängar hon behöver göra för att ta sig ut från isen på högra sidan (östra)? Natalie kommer alltid in på isen på rutan högst upp till vänster, och åker initialt österut (åt höger).
Input
Den första raden innehåller heltalen $R$ och $C$, separerade med ett mellanslag.
De nästa $R$ raderna består av $C$ tecken som var och en beskriver hur en ruta på skridskobanan ser ut. Ett ’.’ innebär att rutan är tom, ’#’ beskriver en ruta med ett hinder.
När Natalie har åkt ut på högra sidan av rinken så är hon klar med turen. Om hon åker ut på någon annan sida av rinken (uppe, nere eller till vänster) så misslyckas hon med sitt mål. Natalie börjar alltid på ruta $(0,0)$ och åker åt höger.
Output
Ditt program ska skriva ut ett tal på en rad - det minsta antal svängar Natalie behöver göra för att ta sig ut från isen på höger sida. Det är garanterat att det finns en lösning.
Förklaring av exempel
I det tredje exemplet (Sample Input 3) så åker Natalie först österut fram till första hindret. Hon svänger sedan höger och åker nedåt. Hon svänger sedan höger igen och åker västerut, för att slutligen svänga höger två gånger till innan hon når den östra kanten av isen. Totalt fyra svängar, svaret är fyra.
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 |
40 |
$3 \le R,C \le 15$ |
|
2 |
30 |
$3 \le R,C \le 30$ |
|
3 |
30 |
$3 \le R,C \le 100$ |
| Sample Input 1 | Sample Output 1 |
|---|---|
6 10 .........# ########.# #........# #.######## #......... ########## |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 3 ... ... ... |
0 |
| Sample Input 3 | Sample Output 3 |
|---|---|
5 5 ....# #.#.. #.... .#..# ##.## |
4 |
