D - Internátny život

Časový limit: 3s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3.4, Python 3.11

Počet bodov: 2

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Spoločnosť MicroLife® sa zaoberá simuláciou jednoduchých foriem života. Momentálne ich pozornosť upútal život na vysokoškolských internátoch v jednej ďalekej krajine, preto sa snažia nasimulovať jeho zjednodušený, no napriek tomu celkom zodpovedajúci, model.

Úloha

Pre zjednodušenie, celá simulácia sa bude odohrávať na 2D mape internátu. Mapa obsahuje MxN štvorcov. Každý štvorec je buď chodba alebo stena. Na mape je niekoľko entít očíslovaných od 1 do P. Každá entita je otočená čelom na jeden zo štyroch smerov (hore, vpravo, dole, vľavo). Entita sa pohybuje v krokoch. V jednom kroku sa posunie na políčko pred ňou, ak je toto políčko chodba, inak sa otočí o 90 stupňov v smere hodinových ručičiek.

Jeden krok entity sa tedá dá popísať nasledujúcimi pravidlami:

Skontroluj políčko pred sebou. Ak je to chodba, choď na krok 2, inak choď na krok 3.
Presuň sa na políčko pred sebou. Koniec kroku.
Otoč sa o 90 stupňov v smere hodinových ručičiek (vpravo bok). Koniec kroku.

Máme dané pozície a otočenia jednotlivých entít v čase T=0. Počas prvej sekundy sa simuluje jeden krok entity číslo 1, počas druhej sekundy jeden krok entity číslo 2, ..., až počas P-tej sekundy jeden krok entity číslo P. V P+1-vej sekunde opäť jeden krok entity 1, v P+2-hej krok entity 2, atď. Vo všeobecnosti, počas k-tej sekundy, kde k=x*P + i (x je nezáporné celé číslo, i je celé číslo od 1 po P) sa simuluje jeden krok entity číslo i. V jednom momente sa na jednom políčku mapy môže naraz nachádzať viacero entít.

Cieľom tejto simulácie je nájsť prvý moment, kedy sa zopakuje nejaká konfigurácia entít. (Konfiguráciou entít rozumieme pozíciu a otočenie každej entity. Entity sú rozlíšiteľné.) Formálnejšie, chceme nájsť najmenší taký počet sekúnd T>0, že existuje S (0 ≤ S < T) také, že konfigurácia po S sekundách od začiatku simulácie je totožná s konfiguráciou po T sekundách od začiatku simulácie. Ak T > 20000 (t.j. žiadna konfigurácia sa do prvých 20000 sekúnd (vrátane) nezopakuje), vypíšte slovo SUPER.

Vstup

Prvý riadok vstupu obsahuje tri prirodzené čísla M,N a P (3 ≤ M,N ≤ 128 a 1 ≤ P ≤ 500). M je počet riadkov, N je počet stĺpcov mapy a P je počet entít. Ďalších M riadkov obsahuje po N znakov. Znak # reprezentuje stenu a znak . (bodka) reprezentuje chodbu. Ľavé horné políčko mapy má pozíciu [1,1] a pravé dolné [M,N]. Okraj mapy tvoria vždy steny.

Ďalej nasleduje P riadkov. Každý z nich obsahuje dve prirodzené čísla Y,X (1≤Y≤M, 1≤X≤N), riadok a stĺpec pozície entity. Môžete predpokladať, že všetky entity sa nacházdajú na chodbe. Entity sú číslované podľa poradia na vstupe. Všetky entity sú na začiatku otočené smerom hore (teda ak stoja na políčku [y,x], tak smerujú na políčko [y-1,x]). Po otočení v smere hodinových ručičiek budú postupne smerovať na políčka [y,x+1],[y+1,x] a [y,x-1].

Výstup

Na výstup vypíšte počet sekúnd, po ktorých sa prvýkrát zopakuje nejaká konfigurácia alebo slovo SUPER, ak sa vrámci prvých 20000 (vrátane) sekúnd žiadna nezopakuje.

Príklad 1

Vstup:

3 3 1
###
#.#
###
2 2

Výstup:

Vysvetlenie:

Na mape je len jedna entita a tá sa nemôže nikam pohnúť. Konfigurácia sa zopakuje, keď sa entita kompletne otočí okolo svojej osi, teda po 4 svojich krokoch, ktoré vykoná počas prvých 4 sekúnd.

Príklad 2

Vstup:

10 10 3
##########
#.#...##.#
#.#...##.#
#.#...##.#
#.#...##.#
#.#...##.#
#.#...##.#
#.######.#
#........#
##########
2 2
2 4
2 9

Výstup:

01 Domáce 2