matrice dreptunghiuri c++

[•IoanP]

Salut!
Stie cineva cum asputea rezolva urmatoarea problema:
O matrice dreptunghiulara
a( a[j]  i=1,n  j=1,m)
contine doar elementele 1 si 0. Elementele 1 reprezinta patratele negre
iar elementele 0 reprezinta patratele albe. Patratelele negre sunt
grupate in dreptunghiuri separate prin cel putin un patratel alb in orice
directie fata de celalalte dreptunghiuri.
Sa se conceapa un algoritm care numara cate dreptunghiuri sunt reprezentate
in matrice.
*
Numarul operatiilor folosite ar trebui sa fie de ordinul n*m
Exemplu:
a(1,1,1,0,0,1,0,0,0,0,
   1,1,1,0,0,1,0,0,0,0,
   0,0,0,0,0,1,0,0,1,1,
   0,1,1,0,0,0,0,0,1,1,
   0,0,0,0,1,0,1,0,0,0)

=>6

?

[•SebiSebi]

Zonele alea formate din pătrate negre trebuie sa aibă forma de dreptunghi? Nu se înțelege exact din enunț. Daca trebuie sa fie dreptunghiuri atunci enunțul problemei e ambiguu. Daca nu, este de ajuns sa folosești un simplu algoritm de fill (parcurgere in latime).

[•IoanP]

Da, zonele formate din patrate negre trebuie sa formeze dreptunghiuri, iar algoritmul trebuie sa calculeze numarul de dreptunghiuri din matrice.

[•SebiSebi]

Pai si dacă ai ceva de genul:

Cod:

1 1 1 1 1
0 1 1 1 0
0 1 1 1 0 

răspunsul e 2 sau 3? Pentru ca poți sa alegi prima linie + ce mai rămâne, sau patratul 3x3 + o celula de 1 + o celula de 1? Dreptunghiurile trebuie sa fie maximale (și dacă da, ce înțelegi prin maximale)?