Záhradný vynález

Tento príklad vyriešilo najmenej tímov.

Skúsim ešte raz zhrnúť zadanie: Máme zadanú mapku a súradnice vchodu. V čase nula položíme začiatok robota na zadané súradnice. Vieme, že robot potrebuje v mapke prejsť dráhu nenulovej dĺžky, to znamená, že v čase 1 sa jeho začiatok presunie na niektoré zo susedných políčok štartového políčka. My máme zrátať minimálny čas, ktorý robot potrebuje na to, aby sa jeho začiatok ocitol opäť na štartovom políčku.

Príklad optimálnej dráhy pre robota dĺžky 5, v mapke zo vzorového vstupu: Štartová bodka na [4,1] znázornená písmenom S.

rrr......
rrrX..XXX
XXrX.....
SrrX..X.X
X..X..X..
.X..XXX..
..X...XX.
X...XXX..
..X...X..

Robot sa bude plaziť do dutiny nad S, lebo to je najbližšie miesto, kde sa dokáže otočiť, a potom sa vráti naspäť na S, čo sa mu podarí na konci štrnástej sekundy (začíname počítať od 0).

Teraz prejdime k tomu, ako sa dá príklad vyriešiť. Základná idea spočíva v tom, že na to, aby sa robot otočil, potrebuje naraziť na cyklus. V tomto cykle sa otočí a vráti sa na štart.

Dve bodky sú susediace, keď sú na mapke bezprostredne vedľa seba, či už horizontálne alebo vertikálne. Jedna bodka môže susediť s najviac 4 ďaľšími bodkami. Vzdialenosť dvoch bodiek je ich Manhatanská vzdialenosť, to znamená súčet absolútnych hodnôt rozdielov ich x-ových a y-ových súradníc.

Cyklus je taká postupnosť bodiek A pozostávajúca z bodiek B0,B2,…,Bn-1, kde N je dĺžka cyklu, v ktorej platia vzťahy:

Žiadne dve bodky z A neležia na tých istých súradniciach na mapke.
Pre ľubovolné i z intervalu <0,n-1> platí: Bi a B(i+1) modulo n sú susediace bodky.
Vzdialenosť cyklu budeme volať číslo vyjadrené vzťahom: Pre všetky i z intervalu <0,n-1> min{vzdialenosť štartovej bodky a bodky Bi}
Z definície cyklu vyplýva, že N je párne číslo.

Keď teda chceme vyrátať dĺžku optimálnej trasy robota s dĺžkou X, musíme z množiny všetkých cyklov na mapke najprv vybrať podmnožinu S, obsahujúcu len cykly, ktoré majú dĺžku N ≥ X (robot sa v nich zvládne otočiť). Optimálnu dĺžku trasy potom dostaneme vzťahom:
Pre všetky C z S: min{2 × (vzdialenosť cyklu C) + dĺžka cyklu C}

Vysvetlenie vzťahu: Ak na otočenie chceme použiť cyklus C, musíme prejsť vzdialenosť medzi najbližším bodom tohto cyklu ku štartu a štartom, potom celý cyklus obísť a nakoniec sa vrátiť späť na štart.

Čo sa týka implementácie vyššie spomínaného postupu, vzorové riešenie funguje takto: Základ je prehľadávanie do šírky. Pre každú bodku, cez ktorú prehľadávanie prechádza, sa určia dĺžky cyklov, ktorých je uvažovaná bodka súčasťou. V globálnom poli sa potom upravuje minimálna zatiaľ nájdená dĺžka trasy pre všetky požadované dĺžky robota. Jednotlivé cykly pre každú bodku hľadáme ďalším prehľadávaním do šírky. Zaujímavá finta je nerobiť toto druhé prehľadávanie až do hĺbky 16 a pozerať sa, či sa nám nejaká vetva požadovanej dĺžky vrátila. Stačí ísť do hĺbky 8 a dlhšie cykly potom skladať spájaním menších vetiev. Samozrejme, že pri oboch metódach si pre každú vetvu treba pamätať, cez ktoré bodky viedla, pretože sa bodky v rámci jednej vetvy nemôžu opakovať, keďže vetva vždy opisuje časť nejakého cyklu.

Alternatívne prístupy k hľadaniu cyklov prechádzajúcich cez danú bodku sú backtracking a prehľadávanie do hĺbky so zväčšujúcou sa maximálnou hĺbkou, na báze ktorých fungovali akceptované riešenia.

Autor: Daniel Švoňava