Test: Симулација процеса Игре живота (The Game of Life)

Park Kalemegdan je najveci park i najvažnija istorijska znamenitost u Beogradu. Ovaj park možemo posmatrati kao tablu dimenzije 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 prede sa jednog praznog polja na drugo prazno polje ako i samo ako ta polja imaju zajednicku ivicu. Medutim, on voli samo spiralne putanje.
Preciznije, Laza bira pocetno prazno polje i pocetni 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 konacno 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 moguce spiralne putanje (N = 6, crni kvadratici 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.