  
   
   
   
   
   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 !
         | 
       |