3. Submatrice binară maximă

Dându-se o matrice binară cu m linii şi n coloane, determinaţi o submatrice pătratică de dimensiune

maximă care are toate elementele egale cu 1.

De exemplu, fie matricea binară următoare:

0 1 1 0 1

1 1 0 1 0

0 1 1 1 0

1 1 1 1 0

1 1 1 1 1

Algoritmul de rezolvare:

1. Notăm cu A[m][n] matricea binară. Subproblemele care vor fi rezolvate constau în determinarea

dimensiunii maxime a unei submatrici pătratice cu toate elementele egale cu 1 care poate fi obţinută în

submatricea care are colţul din dreapta jos în A[i][j].

2. Rezultatele subproblemelor pot fi memorate în matricea S cu m linii şi n coloane, în care:

S[i][j]=dimensiunea maximă a unei submatrice care are colţul din dreapta jos în A[i][j].

Soluţia problemei va fi valoarea maximă a din matricea S.

3. Construirea elementelor din matricea S :

a) Se copiază prima linie şi prima coloană din matricea A în matricea S:

S[i][1]=A[i][1]; i{1,2,...,n}

S[1][j]=A[1][j]; j{1,2,...,n}

b) Pentru celelalte elemente ale matricii S, se folosesc următoarele relaţii de recurenţă:

dacă A[i][j] = 1 atunci

S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1

altfel /* A[i][j] este 0*/

S[i][j] = 0

4. Rezolvarea relaţiilor de recurenţă în manieră bottom-up:

int i, j;

for (i=1; i<=m; i++) S[i][i]=A[i][1];

for (j=1; j<=n; j++) S[1][j]=A[1][j];

for (i=2; i<=m; i++)

for (j=2; j<=n; j++)

if (A[i][j]==0) S[i][j]==0;

else S[i][j]=min(S[i][j-1],S[i-1][j],S[i-1][j-1])+1;}

Pentru matricea binară din exemplul de mai sus, matricea S va avea elementele:

0 1 1 0 1

1 1 0 1 0

0 1 1 1 0

1 1 2 2 0

1 2 2 3 1

Submatricea pătratică de dimensiune maximă

care are toate elementele egale cu 1 este:

1 1 1

1 1 1

1 1 1

Submatricea pătratică de dimensiune maximă are

dimensiunea 3, şi capătul din dreapta jos în A[5][4]:

1 1 1

1 1 1

1 1 1