# PBinfo #1441 – Submatrix – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

După ce a rezolvat problema propusă de tatăl sau, Robert a prins drag de algoritmică. După câteva probleme rezolvate a dat peste o problemă pe care nu a putut-o rezolva. Având o matrice pătratică cu elemente 0 și 1 el trebuie sa afle dimensiunea maximă a unei submatrice pătratice ce conține numai valori 1. Robert este foarte confuz, și vă roagă din nou să îl ajutați. Ca răsplată vă promite 100 de puncte dacă îl ajutați să rezolve și această problemă. Ce ziceți ? Îl ajutăm din nou? 

Cerința
Fiind dată o matrice pătratică de dimensiune n cu valori 0 și 1, să se determine dimensiunea maximă a unei submatrice ce conține numai valori 1.

Date de intrare
Fișierul de intrare submatrix.in conține pe prima linie numărul n reprezentând dimensiunea matricei. Următoarele n linii conțin câte n numere din mulțimea {0,1}.

Date de ieșire
Fișierul de ieșire submatrix.out va conține pe prima linie o valoare naturală L, reprezentând dimensiunea maxima a unei submatrice ce conține numai valori 1.

Restricții și precizări

1 ≤ n ≤ 1000
Pentru 10% din teste n≤10

Exemplul 1
submatrix.in

4
1 1 0 1
1 1 0 0
1 0 1 1
1 1 0 1
submatrix.out

2
Exemplul 2
submatrix.in

4
1 1 1 1
1 1 1 1
1 1 1 0
1 1 1 0
submatrix.out

3

## Cod sursă C++

```cpp
//Solutie problema Matrice
//programare dinamica
//Complexitate N*N
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define dim 1009
using namespace std;
ofstream out("submatrix.out");
int a[dim][dim];
int dp[dim][dim];
int n ;
int sol = 0;
void read();
void debug();
void build();
void solve();
int main()
{
    read();
    build();
    solve();
   // debug();
    out << sol;
}
void read()
{
    ifstream in("submatrix.in");
    in >> n;
    for(int i = 1; i <=n; i++)
        for(int j = 1; j<=n; j++)
            in >> a[i][j];
}
void build()
{
    //first line
    for(int i = 1 ; i<=n ; i++)
        dp[1][i] = a[1][i];
    //first column
    for(int i = 1; i<=n; i++)
        dp[i][1] = a[i][1];
}
void solve()
{
    //pornim de la a[2][2]
    for(int i = 2; i<=n; i++)
        for(int j = 2; j<=n; j++)
        {
            if(a[i][j] == 1)
            {
              dp[i][j] = min(dp[i-1][j],min(dp[i-1][j-1],dp[i][j-1])) + 1;
            }
            else
            {
                dp[i][j] = 0;
            }
        }
    for(int i = 1 ; i<=n; i++)
        for(int j = 1 ; j<=n; j++)
            if(dp[i][j] > sol)
                sol = dp[i][j];
}
void debug()
{
    for(int i = 1;  i<=n ; i++)
    {
        for(int j = 1; j<=n; j++)
            cerr << dp[i][j] << " ";
        cerr << '\n';
    }
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1441)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1441/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1441/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)