Cerința

Se dă o matrice binară (valori 0 și 1). Să se determine care este latura maximă a unui pătrat cu proprietatea că acesta are pe marginea sa doar valori 1.

Date de intrare

Fișierul de intrare lsq.in conține pe prima linie numerele N și M, reprezentând numărul de linii și numărul de coloane ale matricei, apoi N linii, pe fiecare câte M valori 0 sau 1, neseparate prin niciun spațiu, reprezentând elementele matricei..

Date de ieșire

Fișierul de ieșire lsq.out va conține pe prima linie numărul L, reprezentând lungimea maximă a laturii unui pătrat ce conține doar 1 pe marginea sa.

Restricții și precizări

• 1 ≤ N, M ≤ 1000
• Se consideră pătrat și cel de latură 1 (conține doar un element).

Exemplu

lsq.in

7 7
0000000
0111100
0101111
0100101
0111111
0000011
0000011

lsq.out

4

Explicație

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

#include <bits/stdc++.h>
using namespace std;

ifstream cin("lsq.in");
ofstream cout("lsq.out");

int nord[1002][1002] , vest[1002][1002] , n , m , lmax;
char a[1002][1002];

int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
        {
            cin >> a[i][j];
            if(a[i][j] == '1')
            {
                nord[i][j] = a[i][j] - '0' + nord[i-1][j];
                vest[i][j] = a[i][j] - '0' + vest[i][j-1];
            }
        }
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            for(int k = max(lmax , 1) ; k <= m - j + 1 && k <= n - i + 1; k++)
            if(vest[i][j + k - 1] - vest[i][j] + 1 == k && vest[i + k - 1][j + k - 1] - vest[i + k - 1][j] + 1 == k && ///sus si jos
               nord[i + k - 1][j] - nord[i][j] + 1 == k && nord[i + k - 1][j + k - 1] - nord[i][j + k - 1] + 1 == k)///stanga si dreapta
                if(k > lmax) lmax = k;

    cout << lmax;
}