루미 알고리즘

#1368골드Skridskor

PO 2015 온라인 예선코딩출제 Oskar Werkelin Ahlin스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

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.

GruppPoängvärdeGränser
1403 ≤ R,C ≤ 15
2303 ≤ R,C ≤ 30
3303 ≤ R,C ≤ 100

예제

예제 1

입력
6 10
.........#
########.#
#........#
#.########
#.........
##########
출력
4

예제 2

입력
3 3
...
...
...
출력
0

예제 3

입력
5 5
....#
#.#..
#....
.#..#
##.##
출력
4

출처 표기

출처: Programmeringsolympiaden 2015년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.