LSQ

#include <bits/stdc++.h>
#define NMAX 1000
using namespace std;
ifstream fin("lsq.in");
ofstream fout("lsq.out");
int n,m,mat[NMAX][NMAX];

int getMin(int x,int y)
{ return (x<y)?x:y; }

int findSubSquare(int mat[NMAX][NMAX],int N,int M)
{
    int maxv=0;
    int hor[N][M],ver[N][M];
    hor[0][0]=ver[0][0]=(mat[0][0] == 1);
    for(int i=0;i<N;++i)
    {
        for(int j=0;j<M;++j)
        {
            if(mat[i][j]==0)
                ver[i][j]=hor[i][j]=0;
            else
            {
                hor[i][j]=(j==0)?1:hor[i][j-1]+1;
                ver[i][j]=(i==0)?1:ver[i-1][j]+1;
            }
        }
    }
    for(int i=N-1;i>=1;--i)
    {
        for(int j=M-1;j>=1;--j)
        {
            int small=getMin(hor[i][j],ver[i][j]);
            while (small>maxv)
            {
                if (ver[i][j-small+1]>=small&&
                    hor[i-small+1][j]>=small)
                {
                    maxv=small;
                }
                --small;
            }
        }
    }
    return maxv;
}

int main()
{
    int i,j;
    char ch;
    fin>>n>>m;
    fin.get();
    for(i=0; i<n;++i)
        for(j=0;j<m;++j)
        {
            fin>>ch;
            if(ch!='0')
                mat[i][j]=1;
        }
    fout<<findSubSquare(mat,n,m);
    return 0;
}