Este o problema "clasica" de
backtracking in plan care cere determinarea unui
"drum" int-un tablou. Cerinta suplimentara de a nu
mai trece peste aceleasi caractere reduce foarte
mult numarul de mutari - de fapt numarul maxim de
mutari este 26, care reprezinta numarul de
caractere litere mari ale alfabetului.
Pentru a
evita testarea de iesire din tablou am bordat
tabloul cu elementul din coltul stanga-sus - unde
s-a efectuat prima mutare (de aici pleaca piesa).
Pentru
deplasarea in cele 4 directii am folosit 2 vectori
de deplasare.
Evidenta
caracterelor vizitate le-am tinut intr-un vector
viz.
Pseudocodul
-----------
citesc
dimensiunile
citeste
tabela
bordeaza cu
elementul din colt
initializeaza viz, numarul
de mutari (nrm) si numarul maxim de mutari (nrMAX)
apeleaza
procedura Numara (1, 1) //adica pleaca din coltul
stanga-sus
scrie nrMAX
procedura
recursiva Numara (Lin, Col)
{
daca (:-))
caracterul din T[Lin, Col] nu a fost vizitat
{
marcheaza
litera ca ai trecut pe acolo
numara
mutarea
daca ai
gasit mai multe mutari decat pana acum, retine
apeleaza
procedura Numara de 4 ori in cele 4 directii
demarcheaza
litera (pentru alte posibilitati)
decrementeaza numarul de
mutari
}
}
|