La ce s-a gresit ?
In primul rand banuiesc faptul ca problema a fost etichetata dintr-un foc
"usoara" si nu a mai primit o atentie prea mare la implementare. Nu mai este
nevoie sa spun ca acest mod de abordare este total gresit, deoarece problemele
usoare nu trebuie ratate pentru ca acest fapt te costa foarte, foarte scump.
Rezolvarea problemei se baza pe fill, algoritm foarte cunoscut, pe care
nu il prezint deoarece in aproape toate sursele procedura "fill" era prezenta.
Problema avea totusi 2 capcane:
I. Prima dintre ele era legata de gestionarea corecta a stivei. O procedura
de genul "procedure fill(x,y:integer)" este din start gresita, deoarece
nu avem suficient spatiu pe stiva pentru a parcurge in felul acesta
o matrice de 10000 de elemente.
O implementare corecta, pe care o puteti admira in sursa lui
Bogdan Batog este urmatoarea:
procedure fill;
begin
.....
inc(x);fill;dec(x);
dec(x);fill;inc(x);
inc(y);fill;dec(y);
dec(y);fill;inc(y);
.....
end;, unde x si y sunt variabile globale. In acest fel, pe stiva se
aloca numai apelul de procedura (si nici un parametru). Este de retinut
aceasta metoda si pentru alte tipuri de proceduri recursive.
II. A doua capcana era legata de algoritmul folosit in determinarea
peretelui ce trebuie scos. O varianta de genul "scot fiecare perete,
si fac un fill pornind din locul unde se afla peretele pentru a
determina aria camerei rezultate" este total ineficienta, deoarece
mareste in mod drastic complexitatea rezolvarii.
Ideea era ca pentru fiecare element (i,j) din matrice sa cunosc
aria camerei din care face parte, arie[i,j]. Atunci pentru fiecare
perete (x,y), aria camerei ce rezulta prin indepartarea lui este
1+arie[x-1,y]+arie[x+1,y]+arie[x,y-1]+arie[x,y+1]. Bineinteles, se
verifica sa nu adun de doua ori aria aceleasi camere la indepartarea
unui perete. De asemenea aria a[i,j] pentru (i,j) perete este zero.
Acestea fiind spuse, problema este rezolvata.
Concluzia ? Mare atentie la problemele simple !
|
|