题目:
有n行n列的小黑点,还有m条线段连接其中小黑点。统计这些线段练成了多少个正方形(按边长分别统计),从行上到下编号1~~n,列从左到右1~n,。边用Hij,Vij表示,分别代表(i,j)到(i,j+1)这两点之间的边,和(i,j)到(i+1,j)这两点之间的边。

输入输出:
输入n行n列,在输入m条边,m条边用Hij,Vij表示

题目解析:
这道题就是在n*n个点所构成的正方形,以及它输入的m条边的位置,找出一共有多少个正方形,正方形的长度可以不同,Hij也就是在(i,j)这个点向右侧延申一条边出来,Vij也就是(i,j)向下延申一条边。

解题思路:
对于每一个点(i,j)我们依次遍历,记录每一个点向右,以及向下延申的最大长度,放入数组hExp[i][j],和vExp[i][j]中.
hExp[i][j]=hExp[i][j+1]+1，vExp[i][j]=vExp[i+1][j]+1;
也就是,我们从后向前遍历,把后面点能延伸的最大长度,加上自身长度,即我最大能延申长度。

顺序遍历每一个(i,j),依次判断以(i,j)为左上顶点所有可能的正方形边长为s,其中s为1到min(hExp[i][j],vExp[i][j])也就是向右或向下延申的最小值,我们遍历所有长度,找出所有可能的正方形,那么如何判断能否构成一个正方形呢?

我们计算出(i,j)的左下点向右延申的最大值即hExp[i+s][j],和右上点向下延申的最大值,即vExp[i][j+s],只要满足>=s就可以构成正方形。

图解:

代码:

#include<bits/stdc++.h>
#define _for(i,a,b) for(int i=a;i<b;i++)
#define _rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=16;
int n,m,vExp[maxn][maxn],hExp[maxn][maxn],H[maxn][maxn],V[maxn][maxn],Squares[maxn];
int main()
{
    char buf[4];
    int x,y;

    for(int t=1; scanf("%d",&n)==1; t++)
    {
        printf("\n******************************************\n\n");
        //初始化数组
        memset(vExp,0,sizeof(vExp)), memset(hExp,0,sizeof(hExp));
        memset(H,0,sizeof(H)), memset(V,0,sizeof(V)), memset(Squares,0,sizeof(Squares));
        scanf("%d",&m);//读入m条边
        _for(i,0,m)
        {
            //确定m条边位置
            scanf("%s%d%d",&buf,&x,&y);
            if(buf[0]=='H')H[x][y]=1;//输入H则H[i][j]=1
            else V[x][y]=1;//输入V则V[i][j]=1
        }
        //求出每一条边最长能延申多长存放hEXP,vEXP中
        for(int i=n; i>=1; i--)
            for(int j=n; j>=1; j--)
            {
                if(H[i][j]) hExp[i][j]=hExp[i][j+1]+1;//当前边加上,它右侧的边向右延申最大长度
                if(V[i][j]) vExp[i][j]=vExp[i+1][j]+1;//同上,只是向下延申
            }

        _rep(i,1,n)_rep(j,1,n){
            int maxS=min(hExp[i][j],vExp[i][j]);//找出该点,能满足最大正方形
            //遍历所有小于maxS的边,防止一个起点,有多个边长的正方形
            _rep(s,1,maxS){
                if(hExp[i+s][j]>=s&&vExp[i][j+s]>=s){//找出左下点向右延申最大值,以及右上点向下延申的最大值,都要满足>=s才能构成正方形
                    Squares[s]++;//当前s长的正方形++
                }
            }
        }
        printf("Problem #%d\n\n",t);//第t次
        bool found=false;
        _rep(i,1,n) if(Squares[i]){
            found=true;
            printf("%d square(s) of size %d\n",Squares[i],i);//打印长度为i的正方形个数
        }
        if(!found) puts("NO completed squares can be found.");

    }
    return 0;
}

解释代码细节:

#define _for(i,a,b) for(int i=a;i<b;i++)
#define _rep(i,a,b) for(int i=a;i<=b;i++)
定义了两个for循环,第一个i从a开始,i<b,i++,第二个只不过i<=b

memset()初始化数组为0

这道题就解释到这里,希望大家多多支持!
一键三连嘻嘻!