首页 > ACM题库 > HDU-杭电 > hdu 2483 Counting square-枚举-[解题报告]C++
2014
01-26

hdu 2483 Counting square-枚举-[解题报告]C++

Counting square

问题描述 :

There is a matrix of size R rows by C columns. Each element in the matrix is either “0” or “1”. A square is called magic square if it meets the following three conditions.
(1)  The elements on the four borders are all “1”.
(2)  Inside the square (excluding the elements on the borders), the number of “1”s and the number of “0”s are different at most by 1.
(3)  The size of the square is at least 2 by 2.
Now given the matrix, please tell me how many magic square are there in the matrix.

输入:

The input begins with a line containing an integer T, the number of test cases.
Each case begins with two integers R, C(1<=R,C<=300), representing the size of the matrix. Then R lines follow. Each contains C integers, either 0 or 1. The integers are separated by a single space.

输出:

The input begins with a line containing an integer T, the number of test cases.
Each case begins with two integers R, C(1<=R,C<=300), representing the size of the matrix. Then R lines follow. Each contains C integers, either 0 or 1. The integers are separated by a single space.

样例输入:

3
4 4
1 1 1 1
1 0 1 1
1 1 0 1
1 1 1 1
5 5
1 0 1 1 1
1 0 1 0 1
1 1 0 1 1
1 0 0 1 1
1 1 1 1 1
2 2
1 1
1 1

样例输出:

3
2
1

题意:给定一个由0和1构成的n*m矩阵。问矩阵中符合条件的子矩阵有多少个?条件:1.边长大于等于2的正方形;2.四边都没有0;3.除4边外的部分,0和1的个数差小于等于1(这里被自己坑了,我理解成包括四边。。).

题解:用sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+e[i][j].记录(0,0)(0,j)(i,0)(i,j)的矩阵,这样所有的矩阵都能通过容斥原理求得。然后枚举所有的子矩阵的右下端点,接着枚举边长即可。

耗时:796MS/2000MS

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=303;
int sum[maxn][maxn],e[maxn][maxn];
int find(int n,int m)
{
    int i,j,k,ans=0,t=0,p,q;
    if(e[n][m]==0)return 0;
    for(i=n-1,j=m-1;i>=1&&j>=1;i--,j--,t++)
    {
        //判断边上是否有0
        if(!e[i][m]||!e[n][j])return ans;
        for(p=i,q=j;p<n;p++,q++)
            if(!e[i][q]||!e[p][j])break;
        if(p<n)continue;
        //判断边上无0后,计算中间部分0和1个数差
        p=sum[n-1][m-1]-sum[i][m-1]-sum[n-1][j]+sum[i][j];//正方形中部分的和
        if(abs(t*t-2*p)<=1)ans++;
    }
    return ans;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int i,j,k,n,m,ans=0;
        scanf("%d%d",&n,&m);
        memset(sum,0,sizeof(sum));
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                scanf("%d",&e[i][j]);
                sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+e[i][j];//计算以(0,0)和(i,j)为端点的矩阵和
            }
        }
        for(i=2;i<=n;i++)
            for(j=2;j<=m;j++)
                ans+=find(i,j);
        printf("%d\n",ans);
    }
    return 0;
}

解题转自:http://blog.csdn.net/a601025382s/article/details/12383643