Drolca

Apologize To Drolca
随笔 - 28, 文章 - 1, 评论 - 6, 引用 - 0
数据加载中……

hdu 2483 Counting square

#include <iostream>
using namespace std;
int r[301][301];
int c[301][301];
int a[301][301];
int b[301][301];
int rr,cc;
bool check(int i,int j,int k)
{
    
if(r[i][j+k-1]-r[i][j-1]==k)
        
if(r[i+k-1][j+k-1]-r[i+k-1][j-1]==k)
            
if(c[i+k-1][j]-c[i-1][j]==k)
                
if(c[i+k-1][j+k-1]-c[i-1][j+k-1]==k)
                    
return 1;
    
return 0;
}

void slove()
{
    
int i,j,k;
    
int cnt=0;
    
for(i=1;i<=rr;i++)
        
for(j=1;j<=cc;j++)
        
{    
            
for(k=2;k<=rr&&k<=cc;k++)
            
{
                
if(check(i,j,k))
                
{
                    
int sum=b[i+k-1][j+k-1]-b[i-1][j+k-1]-b[i+k-1][j-1]+b[i-1][j-1];
                    
int cnt_1=sum-(k-1)*4;
                    
int cnt_0=(k-2)*(k-2)-cnt_1;
                    
if(abs(cnt_1-cnt_0)<=1)
                        cnt
++;
                }

            }

        }

    printf(
"%d\n",cnt);
}

int main()
{
    
int T;
    scanf(
"%d",&T);
    
while(T--)
    
{
        scanf(
"%d%d",&rr,&cc);
        
int i,j;
        
for(i=1;i<=rr;i++)
            
for(j=1;j<=cc;j++)
            
{
                scanf(
"%d",&a[i][j]);
                b[i][j]
=b[i-1][j]+b[i][j-1]+a[i][j]-b[i-1][j-1];//0 0->i j
                r[i][j]=r[i][j-1]+a[i][j];//r
                c[i][j]=c[i-1][j]+a[i][j];//c
            }

        slove();
    }

    
return 0;
}

posted on 2009-08-29 00:17 Drolca 阅读(122) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理