Problem D
Labyrinten

Din kompis har nyligen börjat spela hitspelet Labyrinter och Ödlor. Spelet går ut på att man går in i en labyrint, där man får slåss mot fiender för att till slut ta sig till bossen (den svåraste fienden). Man får inte se hela labyrinten när man kommer in, utan man måste utforska den för att hitta bossen. Tyvärr leder inte alla vägar rakt till bossen, utan det finns flera vägar som leder till återvändsgränder. Om man vill spela spelet optimalt är det viktigt att använda all information man har för att ta sig till bossen så snabbt som möjligt.

Att det ska gå snabbt är så viktigt att spelare har samlat in ett stort antal labyrintlayouter. Vissa spelare har suttit i timtal och övat på dessa för att bli bättre på att gissa vägen. Du tänker direkt att detta är extremt ineffektivt: även om du inte vet exakt hur labyrinterna skapas, så borde du ha tillräckligt många exempel för att kunna skriva ett program som är bättre än människor.

En labyrint är formad som ett $9 \times 9$ rutnät och kan se ut såhär:

Det finns 4 speciella sorters rum:

• S: detta är rummet där du börjar i labyrinten.

• B: detta rummet innehåller bossen. Målet är att ta sig hit så snabbt som möjligt.

• T: detta rummet innehåller en hemlig skatt. Du är dock inte intresserad av den.

• L: dessa 5 rummen innehåller en spak vardera. Om du går in i rummet och drar i spaken så låses skatten upp och du får reda på vart skattrummet ligger. Notera att du kan gå in i skattrummet även om du inte dragit i spaken, och du bryr dig ändå inte om skatten. Därmed gör det ingen skillnad att dra i spaken förutom att det ger dig information.

Det finns alltså exakt 1 rum med S, B, T och 5 rum med L.

I ett drag kan du gå till ett av de angränsande rummen. Din uppgift är nu att skriva ett program som tar sig till bossen. Du får mer poäng desto färre drag du använder. När programmet startar och efter varje drag du utför får du följande information:

• I vilka av de 4 riktningarna du kan gå.

• Sortens rum du befinner dig i (S, B, T, L eller E). E betyder att rummet inte är speciellt.

• Din position.

• Skattrummets position (om du har dragit i en spak).

Rutnätets rader och kolumner är numrerade på följande vis:

Interaktion

När ditt program startar och efter varje gång du gjort ett drag ska ditt program läsa in en rad på följande format:
LURD K $\, p_r$ $\, p_c$ $\, t_r$ $\, t_c$

Med följande betydelse:

• L,U,R,D är alla 0 eller 1.

• Om L är 1, så kan du gå åt vänster, annars inte.

• Om U är 1, så kan du gå uppåt, annars inte.

• Om R är 1, så kan du gå åt höger, annars inte.

• Om D är 1, så kan du gå nedåt, annars inte.

• K beskriver sortens rum du befinner dig i. Detta kommer alltid vara en av S, B, T, L och E, vars betydelse beskrivs ovan.

• $p_r$ är raden som du befinner dig på.

• $p_c$ är kolumnen som du befinner dig på.

• $t_r$ är raden där skattrummet finns. Om du inte har dragit i en spak än är detta istället -1.

• $t_c$ är kolumnen där skattrummet finns. Om du inte har dragit i en spak än är detta istället -1.

För att göra ett drag, skriv ut en bokstav som indikerar vilken riktning du vill gå åt: < (höger), > (vänster), V (ner), eller ^ (upp). Läs sedan in informationen igen, gör sedan ett drag och så vidare tills du når bossen.

Om du någonsin läser in att K är B, det vill säga att du är vid bossen ska ditt program avslutas. Om du inte gör det kan du få konstiga fel.

Om du någonsin går in i ett rum med en spak kommer du att dra i den automatiskt.

Om du försöker gå i en riktning du inte kan kommer du att få Wrong Answer.

Se till att flusha outputen efter varje drag, annars kan du få Time Limit Exceeded. I C++ kan detta göras med exempelvis cout << flush eller fflush(stdout); i Python med stdout.flush(); och i Java med System.out.flush().

Poängsättning

Din lösning kommer att testas på flera testfall. Låt ”moves” vara antalet drag du utför för att nå bossen. Poängen för ett givet testfall beräknas då enligt följande formel:

• Om $\text{moves} \leq 24$ får du $\min (100, 170-7 \cdot \text{moves})$ poäng.

• Annars, om $\text{moves} \leq 1000$ får du 1 poäng.

• Annars får du 0 poäng.

Det totala antalet poäng du får är genomsnittet av poängen över alla testfall.

Under tävlingen kommer du att testas på exakt 30 testfall. När tävlingen är över kommer din lösning att köras om med 70 andra testfall. Det är garanterat att de 70 fallen i slutet av tävlingen är jämförbara med de 100 fallen som används under tävlingen.

Nedladdningar

Längst ned på hemsidan kan du ladda ner labyrint.zip. I denna finns 10000 testfall som genererats på samma vis som datan som används på Kattis. Det finns även andra hjälpsamma program.

Exempel

Nedan visas en interaktion mellan domaren och ett program som löser exempelfallet som visas i bilden ovan.

0101 S 3 3 -1 -1

^

0011 E 2 3 -1 -1

>

1100 E 2 4 -1 -1

^

0001 L 1 4 2 2

V

1100 E 2 4 2 2

<

0011 E 2 3 2 2

V

0101 S 3 3 2 2

V

1110 E 4 3 2 2

>

1101 E 4 4 2 2

V

0101 E 5 4 2 2

V

1100 E 6 4 2 2

<

1111 E 6 3 2 2

V

1110 E 7 3 2 2

>

1010 E 7 4 2 2

>

1010 E 7 5 2 2

>

1100 E 7 6 2 2

^

0001 B 6 6 2 2