Pascal - zanimljiv zadatak

evo ovako: zadatak je u vezi dvodimenzionalnog niza

upišemo dvodimenzionalni niz koja bi nacrtana izgledala npr. ovako:

0 1 1 1 0 0 1 0 0 0

0 1 0 0 0 0 1 0 0 0

0 1 0 0 0 0 1 0 1 0 

0 1 1 1 0 0 1 1 1 1

0 0 0 1 0 0 0 0 1 0

0 0 0 1 0 0 0 0 1 0

0 1 1 1 0 0 0 0 1 0

ovo izgleda bezveze ali ako bolje pogledate ja sam od jedinica ispisao broj 54,

tako da je onda zadatak da nakon što upišemo čitavi niz, program bi trebao provjeriti ima li u nizu znamenaka upisanih na ovaj način i naravno da onda te znamenke ispiše

ideje?? 

Ime algoritma je(rekurzije) "flood fill"  bar tako mislim(radilo se o zadatku u c-u , ali natjecatelji su imali izbor ili c ili pascal)....ja sam ga našao kad sam davno s c-om bio na ti , kao primjer s takmičenja ACM-a (međunarodno takmičenje).Možda i nije , ali neka me isprave i daju ti točnu informaciju algoritma.

Algoritam trazenja se zove breadth-first, prvu celiju tretiras kao root stabla.

Btw, ako ukljucis heuristicku funkciju koja kao izvor koristi patterne, dobit ces Astar, inace vrlo popularan search algoritam - vecinom nepravedno ogranicen samo na pathfinding.

Jednostavno, s obzirom da je array 2D, znas koordinate izvorisne tocke, i mozes provjeriti sve ostale patterne da vidis gdje imas crna polja. Npr ako u niti jednom patternu nemas crno polje gore-lijevo, a u vecini patterna je crno polje ravno dolje, onda znas u kojem smjeru ici. Na isti nacin na koji je u A*-u heuristika obicna manhattan duljina, tako ovdje mozes dodijeliti najvise bodova nodeu koji ima crno polje u tom smjeru u najvise razlicitih patterna.

A* pretrazuje sve _okolne_ tocke prvo. Ako ti nije jasno, rado cu ti poslati mali prototip.

Dovoljno je ukloniti heuristicku funkciju i vidjet ces vrlo brzo da pretrazuje prvo okolne tocke, a ne shiba u jednom smjeru koliko god duboko moze. TJ. makni heuristiku i imas tipicni breadth first.