Monstrum v bludišti

Zadáno v pátek 9. 10.

K odevzdání ve čtvrtek 15. 10.

V bludišti reprezentovaném maticí políček se nachází příšera. Příšera je v každém kroku na jednom políčku a je otočená jedním ze čtyř možných směrů - nahoru, doprava, dolů nebo doleva.

V každém kroku výpočtu příšera udělá jeden tah, možné tahy jsou: otočit se doprava, otočit se doleva nebo postoupit kupředu, tj. přejít na sousední políčko ve směru otočení. Na začátku má příšera po pravé ruce zeď a pohybuje se tak, aby pravou rukou stále sledovala tuto zeď (viz příklad).

Vstup programu obsahuje nejdříve šířku a výšku a potom mapu bludiště. Jednotlivé znaky představují jednotlivá políčka mapy: X znamená zeď, . znamená volné políčko a znaky ^, >, v nebo < znamenají volné políčko, na kterém právě teď stojí příšera, otočená směrem nahoru, doprava, dolů nebo doleva, v tomto pořadí.

Program načte popis bludiště a potom dvacetkrát pohne příšerou a po každém pohybu vytiskne mapu bludiště ve stejném tvaru, jako ji načetl. Výpis mapy bude vždy ukončen prázdným řádkem.

O správnost tohoto vstupu (tj. o to, že zadané rozměry bludiště opravdu danému bludišti odpovídají, že v něm je právě jedno monstrum atp) se stará uživatel. Stejně tak celé bludiště kreslí on sám. Vy ho jen dostanete a simulujete v něm dvacet kroků monstra.

Postup (čtěte pozorně)

Úkol si rozdělte na čtyři části (které budou zhruba odpovídat čtyřem nebo více nezávislým funkcím):

  1. Čtení vstupu od uživatele a převod tohoto tzv. počátečního stavu na nějakou datovou strukturu (např. seznam seznamů nebo tak)
  2. Funkce, která dostane nějaký stav a vrátí stav následující (tj. v podstatě simuluje jeden jeden krok monstra)
  3. Funkce, která funkci číslo dva zavolá dvacetkrát
  4. Vypsání současného stavu (tahle funkce se bude volat po každém kroku funkce 2.)

Každá část by měla fungovat nezávisle na těch ostatních — například funkci z bodu 2. by mělo být jedno, jestli stav bludiště, který dostala, pochází ze vstupu, z textového souboru, nebo zcela odněkud jinud.

Určitě tím pádem nepište všechen kód do jedné funkce, nebo dokonce bez použití funkcí. Pokud vám ohledně tohoto něco není jasné, klidně se ptejte :-) Případné chyby v této části vám budu vracet k opravení.

Příklady vstupů a výstupů

Od uživatele dostanete vstup:

10
6
XXXXXXXXXX
X....X...X
X....X...X
X.X..X.X.X
X.X.>..X.X
XXXXXXXXXX

Vypíšete následující výstup:

XXXXXXXXXX
X....X...X
X....X...X
X.X..X.X.X
X.X..>.X.X
XXXXXXXXXX

XXXXXXXXXX
X....X...X
X....X...X
X.X..X.X.X
X.X...>X.X
XXXXXXXXXX

XXXXXXXXXX
X....X...X
X....X...X
X.X..X.X.X
X.X...^X.X
XXXXXXXXXX

XXXXXXXXXX
X....X...X
X....X...X
X.X..X^X.X
X.X....X.X
XXXXXXXXXX

XXXXXXXXXX
X....X...X
X....X^..X
X.X..X.X.X
X.X....X.X
XXXXXXXXXX

XXXXXXXXXX
X....X...X
X....X>..X
X.X..X.X.X
X.X....X.X
XXXXXXXXXX

XXXXXXXXXX
X....X...X
X....X.>.X
X.X..X.X.X
X.X....X.X
XXXXXXXXXX

XXXXXXXXXX
X....X...X
X....X..>X
X.X..X.X.X
X.X....X.X
XXXXXXXXXX

XXXXXXXXXX
X....X...X
X....X..vX
X.X..X.X.X
X.X....X.X
XXXXXXXXXX

XXXXXXXXXX
X....X...X
X....X...X
X.X..X.XvX
X.X....X.X
XXXXXXXXXX

XXXXXXXXXX
X....X...X
X....X...X
X.X..X.X.X
X.X....XvX
XXXXXXXXXX

XXXXXXXXXX
X....X...X
X....X...X
X.X..X.X.X
X.X....X>X
XXXXXXXXXX

XXXXXXXXXX
X....X...X
X....X...X
X.X..X.X.X
X.X....X^X
XXXXXXXXXX

XXXXXXXXXX
X....X...X
X....X...X
X.X..X.X^X
X.X....X.X
XXXXXXXXXX

XXXXXXXXXX
X....X...X
X....X..^X
X.X..X.X.X
X.X....X.X
XXXXXXXXXX

XXXXXXXXXX
X....X..^X
X....X...X
X.X..X.X.X
X.X....X.X
XXXXXXXXXX

XXXXXXXXXX
X....X..<X
X....X...X
X.X..X.X.X
X.X....X.X
XXXXXXXXXX

XXXXXXXXXX
X....X.<.X
X....X...X
X.X..X.X.X
X.X....X.X
XXXXXXXXXX

XXXXXXXXXX
X....X<..X
X....X...X
X.X..X.X.X
X.X....X.X
XXXXXXXXXX

XXXXXXXXXX
X....Xv..X
X....X...X
X.X..X.X.X
X.X....X.X
XXXXXXXXXX