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

#include <bits/stdc++.h>
using namespace std;
ifstream cin("submatrix.in");
ofstream cout("submatrix.out");
int n , a[1001][1001] , d[1001][1001] , maxi;
int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= n ; ++j)
    {
        cin >> a[i][j];
        if(i==1) d[1][j]=a[i][j];
        else if(j==1) d[i][1]=a[i][j];
    }
    for(int i = 2 ; i <= n ; ++i)
        for(int j = 2 ; j <= n ; ++j)
        {
            if(a[i][j]==1) d[i][j]=min(d[i-1][j] , min(d[i-1][j-1] , d[i][j-1]))+1;
            if(d[i][j]>maxi) maxi=d[i][j];
        }
    cout << maxi;
}