루미 알고리즘

#1412골드Rätblocket

PO 2016 학교 예선코딩출제 Erik Odenman스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Rätblocket är ett mobilspel som snabbt har blivit otroligt populärt. Spelet går ut på att man genom att vinkla mobilen åt olika håll ska få ett rätblock att rulla från cell A till cell B på en bana. Rätblocket har storlek 1x1x2 och banan är ett tvådimensionellt bräde med celler av storlek 1x1. Vissa celler är fria, vilket betyder att rätblocket kan röra sig fritt på dem, medan vissa celler är blockerade. Det är inte möjligt att röra sig utanför banan.

Beroende på om rätblocket står upp eller ligger ner så ockuperar det 1 eller 2 celler. I början av spelet så står blocket upp i cellen markerad med ett A och målet är att flytta det så att det står i cellen markerat med ett B (det räcker alltså inte med att halva blocket ligger på cell B). En förflyttning av blocket kan göras i 4 olika riktningar - upp, ner, höger eller vänster - och en förflyttning gör att blocket rullar över i den givna riktningen (givet att det inte är en blockerad cell i vägen eller banan tar slut). För att tydligare visa hur en förflyttning går till så är här början på en lösning till exempelfall 1:

(그림은 원문 저장소에서 볼 수 있습니다)

Figur 1: Halva lösningen till det första exempelfallet. Rätblocket flyttas först ett steg till höger, sedan två steg nedåt och till sist ett steg åt vänster.

På mer avancerade banor så förekommer även så kallade modulo-celler. Dessa är celler som kan befinna sig i två olika tillstånd, 0 eller 1. I tillstånd 0 så beter sig en modulo-cell precis som en fri cell som rätblocket kan röra sig på. I tillstånd 1 så är dock modulo-celler upphöjda och beter sig som blockerade celler. Det kan även finnas växel-celler (markerade med ett c) utplacerade på banan. När rätblocket ställs på en växel-cell så ändras tillstånden på alla modulo-celler (0 blir till 1 och vice versa).

(그림은 원문 저장소에서 볼 수 있습니다)

Figur 2: Det tredje exempelfallet, före och efter att växeln har aktiverats.

Banorna är designade så att det alltid finns en giltig lösning. Din uppgift är att beräkna det minsta antal förflyttningar som behövs för att lösa en bana.

Indata

Du kommer först att få två heltal N och M. Detta betyder att banan har N rader och M kolumner. De följande N raderna har M tecken var och beskriver hur banan ser ut. Följande tecken kan förekomma:

  • A eller B: beskriver banans start- respektive slut-positioner.
  • . (en punkt): beskriver en fri cell.
  • #: beskriver en blockerad cell.
  • 0 eller 1: beskriver en modulo-cell med givet start-tillstånd.
  • c: beskriver en växel-cell

Det är garanterat att varje bana innehåller precis ett A och ett B.

Utdata

Skriv ut en rad med ett heltal, det minsta antal förflyttningar som behövs för att flytta rätblocket från cell A till cell B.

Poängsättning

För testfall värda 40 poäng så har en bana upp till 7 rader och 7 kolumner, men inga modulo-celler.

För de resterande 60 poängen så behöver din lösning även kunna hantera modulo-celler.

예제

예제 1

입력
3 3
A..
...
..B
출력
8

예제 2

입력
3 5
A#...
.....
...#B
출력
14

예제 3

입력
3 7
A..#...
.B.1...
..c#...
출력
27

출처 표기

출처: Programmeringsolympiaden 2016년 학교 예선 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.