Zadanie

Jesenné čakanie

Počet bodov: 80

Keďže Andrej stále čaká na 6. vydanie hry KSP¹, rozhodol sa oprášit svoju starú kolekciu hier. Medzi nespočetnou kolekciou hier našiel aj staré vydanie Pytónu 3, na ktorú má bohaté spomienky zo svojho detstva.

V tom si ale spomenul, že mal pripraviť úlohu do Zenitu a tak sa rozhodol túto epickú hru zazdielať aj Vám.

Podarí sa vám prekonať Andrejov rekord?

Úloha

Na vstupe dostanete počiatočnú pozíciu hadíka Pytóna: \(y\), \(x\), rozmery mapy: \(h\), \(w\) a popis jabĺčok.

Vašou úlohou je hrať Andrejovu hru a získať čo najviac jabĺčok. Hadík má na začiatku dĺžku 1.

V každom ťahu sa viete pohnúť do jedného zo štyroch smerov, čím sa hadík posunie — zaberie políčko smerom, ktorým sa hýbe a opustí posledné políčko na ktorom bol jeho chvost.

V prípade že políčko, kde je jeho hlava, bude obsahovať jabĺčko, dĺžka hadíka sa zvýši o jedna (teda jeho chvost sa v tom ťahu nepohne). V kóde použi premennú snakeLenght.

Bodky sa zjavujú na začiatku hry a medzi ťahmi. Je garantované, že jabĺčka sa zjavia iba na prázdnom políčku. Na mape vždy existuje nezáporný počet jabĺčiek.

Skóre je aktuálna dĺžka hadíka. Hra končí, ak hadík narazí sám do seba, vyjde von z mapy, alebo ak nastane maximálny počet ťahov.

Pre príklady pohybu pozri sekciu Príklady.

Vstup a Výstup

Prvý riadok vstupu obsahuje počiatocnú pozíciu hadíka a veľkosť mapy \(0 \leq y, x < h, w \leq 10^4\).

Potom nasledujú riadky niekoľkých typov:

• * y x - pribudlo nove jabĺčko na pozícií \(x\), \(y\)
• ? - rozhodni sa, kam sa chceš pohnúť
• . - koniec hry (po prečítaní tohto riadku by mal tvoj program hneď skončiť)

Na požiadavku typu ? odpovedaj smerom, kam sa chceš pohnúť, teda riadkom s jedným z nasledovných znakov:

• ^
• v
• >
• <

Keďže táto úloha je interaktívna, po vypísaní každého pohybu je nutné flushovať. V Pythone sa to robí parametrom print-u flush: print(..., flush = True), v C++ pomocou std::cout.flush().

Obmedzenia

Navyše v prvej sade sa väčšina jabĺčok spawnuje hneď pri hlave hadíka.

Bodovanie

Body sa odvíjajú od výslednej dĺžky vášho hadíka Pytóna.

Celkovo približne \(85\%\) bodov viete dostať keď naprogramujete riešenie podobne dobré, ako Andrejove², na danej konfigurácií mapy. Za horšie riešenie dostanete počet bodov približne lineárne závislý od toho, ako ste sa priblížíli k Andrejovemu riešeniu. Naopak, za lepšie riešenie viete dostať aj ďalšie (bonusové) body³.

Plný počet bodov dostanete, ak prekonáte Andrejove skóre na danej konfigurácií mapy. V opačnom prípade sa počet bodov odvíja od toho, ako blízko je vaše skóre k Andrejovmu.

Príklady

0 0 4 4
* 0 1
* 0 2
?
>
* 2 3
?
>
* 3 3
?
>
?
v
?
v
.

Stav mapy v ťahoch je nasledovný (\((0, 0)\) je ľavý horný roh):

#**.
....
....
....

##*.
....
...*
....

###.
....
...*
...*

.###
....
...*
...*

..##
...#
...*
...*

..##
...#
...#
...*

Skóre hadíka na konci je 4.

1 0 2 3
* 0 1
?
>
?
^
* 1 2
?
v
.

Tento hadík zomrel po v príkaze, lebo narazil sám na seba. Stavy boli nasledovné:

.*.
#..

.*.
.#.

.#.
.#*

Skóre hadíka na konci je 2.