cntSQ_80puncte

#include <fstream>
#define NMAX 1000
using namespace std;
ifstream fin("cntsq.in");
ofstream fout("cntsq.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 TOTAL=0,NR;
    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>=0;--i)
    {
        for(int j=M-1;j>=0;--j)
        {
            int small=getMin(hor[i][j],ver[i][j]);
            NR=0;
            while(small>0)
            {
                if(ver[i][j-small+1]>=small&&
                    hor[i-small+1][j]>=small)
                {
                    ++NR;
                }
                --small;
            }
            TOTAL+=NR;
        }
    }
    return TOTAL;
}

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;
}