Asociem problemei un graf neorientat
astfel:
multimea
cainilor reprezinta multimea varfurilor grafului
exista
muchie intre nodul a si nodul b daca cainii a si b
se dusmanesc.
Vom
reprezenta graful prin liste de adiacenta.
G[a][0]=numarul de caini
cu care se dusmaneste cainele a
G[a][i]= al
i -lea caine cu care se dusmaneste cainele a.
Numim
configuratie o multime de caini aflati pe un
anumit mal.
Mai exact o
configuratie este o structura cu doua campuri:
mal care
poate fi 0 sau 1
T care este
vectorul caracteristic al multimii cainilor
situati pe malul mal.
O astfel de
reprezentare este costisitoare ca memorie, prin
urmare, pentru a memora toate
configuratiile corecte vom
reprezenta o configuratie condensat, ca un nr.
Putem
considera vectorul caracteristic ca fiind
reprezentarea binara a unui numar
si retinem
numarul respectiv in baza 10, la care adaugam
malul drept cea mai semnificativa cifra din
reprezentare.
Pentru a
utiliza toate configuratiile de caini valide (deci
in care oricare doi caini nu se dusmanesc)
putem
utiliza metoda backtracking sau un algoritm de tip
succesor.
Configuratiile valide
generate sunt retinute in forma condensata in
vectorul c.
Pe parcursul
generarii vom retine si max (numarul maxim de
caini care nu se dusmanesc, deci
care pot fi
lasati singuri pe acelasi mal.
Numarul
minim de locuri este minloc=n-max+1 (daca putem
gasi o schema de transport cu n-max+1 locuri in
barca) sau minloc=n-max+2 (in caz contrar).
Pentru a
genera o schema de transport a cainilor vom
considera configuratiile valide ca fiind varfurile
unui graf.
Exista arc
de la configuratia i la configuratia j in acest
graf daca din configuratia j se poate ajunge in
configuratia i
cu o barca
cu minloc locuri.
Vom parcurge
BFS acest graf plecand din configuratia finala
(configuratia 0, in care nu exista nici un caine
pe malul 0, malul de plecare), pana cand ajungem
in configuratia initiala (configuratia 1, in care
nu exista nici un caine pe malul 1).
In timpul
parcurgerii BFS retinem pentru fiecare
configuratie si nr minim de traversari necesare
pentru configuratia respectiva.
Pentru
evaluare au fost utilizate 10 teste (numerotate de
la 0 la 9) si s-au acordat 10 puncte pe test.
|