习题4-2 正方形（Squares, ACM/ICPC World Finals 1990, UVa201）
有n行n列（2≤n≤9）的小黑点，还有m条线段连接其中的一些黑点。统计这些线段连成
了多少个正方形（每种边长分别统计）。
行从上到下编号为1～n，列从左到右编号为1～n。边用H i j和V i j表示，分别代表边
(i,j)-(i,j+1)和(i,j)-(i+1,j)。如图4-5所示最左边的线段用V 1 1表示。图中包含两个边长为1的正
方形和一个边长为2的正方形。
Sample Input
4
16
H 1 1
H 1 3
H 2 1
H 2 2
H 2 3
H 3 2
H 4 2
H 4 3
V 1 1
V 2 1
V 2 2
V 2 3
V 3 2
V 4 1
V 4 2
V 4 3
2
3
H 1 1
H 2 1
V 2 1
Sample Output
Problem #1
2 square (s) of size 1
1 square (s) of size 2
**********************************
Problem #2
No completed squares can be found.
思路：
先看输入的数据：
H输入的是行列的点往右连的一条边
V输入的是列行的点往下连的一条边
1、我们先用两个二维数组记录下输入的点的坐标，一个H（水平），一个V（垂直）。比如右边的点就记为1。
2、写个函数，传进参数为查找的方块的边长。
3、然后从第一个点开始遍历。判断以这个点作为左上顶点的正方形，的四条边是不是存在，即标志四条边的点的值是不是1。
4、关于大于1的边长来说，我们可以在判断时用个循环，每次循环判断的是边长中的一部分（一个单位长度）的边是不是存在。即可。
5、具体看代码吧。
#include<iostream>
#include<cstring>
using namespace std;
int hor[10][10],ver[10][10];
int N;
int square(int sq_n)
{
//cout<<sq_n<<"sq_n"<<endl;
int sqnum=0,iff=0;
for(int x=1;x<=N-sq_n;x++)
{
for(int y=1;y<=N-sq_n;y++)
{
//cout<<hor[x][y]<<" "<<ver[x][y]<<endl;
for(int i=0;i<sq_n;i++)//判断大于1边长正方形
if(hor[x][y+i]&&hor[x+sq_n][y+i]&&
ver[x+i][y]&&ver[x+i][y+sq_n])
iff=1;//成方块
else
{
iff=0;//不成方块
break;
}
if(iff)
sqnum++;//方块的个数
}
}
return sqnum;
}
int main()
{
int T,TN=1;
while(cin>>N>>T)
{
if(TN>1)
cout<<endl<<"**********************************"<<endl<<endl;
cout<<"Problem #"<<TN++<<endl<<endl;
memset(hor,0,sizeof(hor));
memset(ver,0,sizeof(ver));
while(T--)//记录点的信息
{
char hv;
int x,y;
cin>>hv>>x>>y;
if(hv=='H')
hor[x][y]=1;
else
ver[y][x]=1;//注意ver的是反的
}
int num;
int ifn=0;
for(int i=1;i<=N;i++)
{
num = square(i);
if(num)
{
cout<<num<<" square (s) of size "<<i<<endl;
ifn++;
}
}
if(!ifn)
cout<<"No completed squares can be found."<<endl;
}
return 0;
}
//AC at 2018/3/4
（题外话：到校第一道题还算顺利。祝福接下来的旅程吧。算法真害人。）