Cel mai mare pătrat de 1 într-o matrice, în C++

Într-o matrice de zero și unu, vrem cel mai mare pătrat format numai din celule cu valoarea 1. Pătratul trebuie să aibă laturile paralele cu cele ale matricei. Nu este suficient să numărăm toate valorile 1: ele pot fi răspândite fără să formeze un pătrat mare.

Starea fixează un colț

Programarea dinamică memorează soluții pentru porțiuni mai mici. dp[i][j] este latura celui mai mare pătrat de 1 al cărui colț dreapta jos este celula a[i-1][j-1]. Folosim o linie și o coloană suplimentare de zero pentru a trata uniform marginile.

Citim 1≤n,m≤100 și o matrice cu valori 0 sau 1. Afișăm latura maximă și aria ei. Dacă nu există niciun 1, ambele valori sunt zero. Indicii datelor a încep de la zero; indicii stărilor utile dp încep de la 1.

De ce luăm minimul a trei vecini

Dacă celula curentă este zero, nu poate fi colțul unui pătrat de 1 și starea rămâne zero. Dacă este unu, putem extinde numai atât cât permit pătratele din sus, stânga și diagonala stânga sus. Luăm minimul celor trei laturi și adăugăm unu.

Vecinul diagonal nu poate fi omis. În matricea 0 1 / 1 1, celula dreapta jos are vecini de sus și stânga egali cu 1, dar nu există un pătrat 2×2 plin. Diagonala zero blochează extinderea greșită.

În matricea 0,1 / 1,1, există trei valori 1, dar niciun pătrat 2×2 plin. La colțul dreapta jos, minimul celor trei stări vecine este zero.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n,m; cin >> n >> m;
    int a[100][100],dp[101][101]={},maxim=0;
    for(int i=0;i<n;++i) for(int j=0;j<m;++j) cin >> a[i][j];
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(a[i-1][j-1]==1) {
        dp[i][j]=1+min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]});
        maxim=max(maxim,dp[i][j]);
    }
    cout << maxim << ' ' << maxim*maxim << '\n';
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării și aceleași rezultate. Tabloul clasic rezervă capacitatea maximă; vectorul construiește numărul de elemente necesare. Indicii folosiți de algoritm rămân aceiași.

#include <vector>

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n,m; cin >> n >> m;
    vector<vector<int>> a(n,vector<int>(m)),dp(n+1,vector<int>(m+1)); int maxim=0;
    for(int i=0;i<n;++i) for(int j=0;j<m;++j) cin >> a[i][j];
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(a[i-1][j-1]==1) {
        dp[i][j]=1+min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]});
        maxim=max(maxim,dp[i][j]);
    }
    cout << maxim << ' ' << maxim*maxim << '\n';
}

Ce garantează tranziția

Cele trei pătrate vecine acoperă partea veche a unui pătrat extins, iar celula curentă completează colțul. Cel mai mic vecin limitează extinderea: un pătrat mai mare ar cere o zonă de 1 pe care acel vecin nu o poate furniza.

Răspunsul este maximul tuturor stărilor, nu neapărat dp[n][m]. Pătratul cel mai mare se poate afla oriunde în matrice. Aria se calculează abia după alegerea laturii, prin latură·latură.

Timpul este O(n·m), fiecare stare fiind calculată o singură dată. Memoria este O(n·m). Tabloul clasic dp are capacitate 101×101 pentru marginea suplimentară, iar varianta vector alocă (n+1)×(m+1).

Exersează

Matricea 2×2 plină cu 1 produce 2 4. Matricea 0 1 / 1 1 produce 1 1. O matrice numai cu zero produce 0 0. Verifică și un pătrat maxim aflat în stânga sus, departe de ultima celulă.

Continuă cu programarea dinamică pe matrice, sumele prefix 2D și indicii matricelor.

Întrebări frecvente

Ce reprezintă dp[i][j] la pătratul maxim de unu?

Latura celui mai mare pătrat de celule cu valoarea 1 care se termină în colțul dreapta jos corespunzător. Nu reprezintă aria și nici numărul tuturor valorilor 1 dintr-un prefix.

De ce folosim minimul dintre trei vecini în tranziție?

Un pătrat mai mare cere sprijin de sus, din stânga și din diagonală. Cea mai mică dintre cele trei laturi limitează extinderea; pentru o celulă cu 1 se adaugă apoi o unitate.

Cum obțin aria celui mai mare pătrat?

Păstrează cea mai mare latură calculată și ridic-o la pătrat. Dacă matricea nu conține niciun 1, latura și aria sunt ambele zero.