Test: Složenost algoritama

Park Kalemegdan je najveći park i najvažnija istorijska znamenitost u Beogradu. Ovaj park možemo posmatrati kao tablu dimenzija N × N sa N2 (kvadratnih) polja. Na nekim poljima se nalaze fontane a sva ostala polja su prazna. Mali Laza voli da vozi bicikl kroz park – on može da pređe sa jednog praznog polja na drugo prazno polje ako i samo ako ta polja imaju zajedničku ivicu. Međutim, on voli samo spiralne putanje.
Preciznije, Laza bira početno prazno polje i početni smer (Sever, Istok, Zapad ili Jug). Zatim se pomeri za bar jedno polje u izabranom smeru, skrene 90 stepeni udesno, pomeri se za bar jedno polje u novom smeru, zatim ponovo skrene 90 stepeni udesno, ponovo se pomeri za bar jedno polje u novom smeru, i konačno skrene 90 stepeni udesno i pomeri se za bar jedno polje u novom smeru.
On ne sme da vozi preko polja sa fontanom i ne sme da vozi preko istog praznog polja više od jednom. Takva putanja se zove spiralna putanja i njena dužina je broj polja te putanje. Slika 1 prikazuje primer parka i neke moguće spiralne putanje (N = 6, crni kvadratići predstavljaju polja sa fontanom).

Koja je dužina Lazine putanje ako je poznato da on uvek bira najdužu spiralnu putanju?

Morate biti ulogovani kako biste radili test.