//第33届ACM-ICPC亚洲预选赛成都赛区解题报告
Problem J
Counting Square
//o(n^2)处理，o(n^3)枚举
#include<iostream>
using namespace std;
int mat[301][301];
int sum[301][301];
int main()
{
int t;
int r,c;
int res=0;
int i,j,k;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&r,&c);
memset(sum,0,sizeof(sum));
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
{
scanf("%d",&mat[i][j]);
if(mat[i][j]==0) mat[i][j]=-1;
sum[i][j]=mat[i][j]-sum[i-1][j-1]+sum[i-1][j]+sum[i][j-1];
}
res=0;
for(i=1;i<r;i++)
for(j=1;j<c;j++)
{
if(mat[i][j]==-1 || mat[i][j+1]==-1 || mat[i+1][j]==-1 ) continue;
int all=0,bo=0,in=0;
for(k=1;i+k<=r && j+k<=c;k++)
{
all=sum[i+k][j+k]-sum[i+k][j-1]-sum[i-1][j+k]+sum[i-1][j-1];
in=sum[i+k-1][j+k-1]-sum[i+k-1][j]-sum[i][j+k-1]+sum[i][j];
bo=all-in;
if(bo<4*k) continue;
else if(in<=1 && in>=-1) res++;
}
}
printf("%d\n",res);
}
return 0;
}posted on 2009-09-09 23:49
wyiu 阅读(223)
评论(0) 编辑 收藏 引用