UVa 201 Squares-程序员充电站

题目分析

本题是一个计算正方形数量的模拟问题。给定一个由点阵构成的网格，以及一些连接相邻点的水平线段（H）和垂直线段（V），需要统计该网格中所有不同边长的正方形的数量。

例如，当n=4n = 4n=4时，共有161616个点，输入若干条线段后，需要输出边长为1,2,…,n−11, 2, \dots, n-11,2,…,n−1的正方形各有多少个。

解题思路

1. 数据结构设计

由于n≤9n \leq 9n≤9，网格规模很小，可以直接使用三维数组存储线段信息：

row[i][j][k]表示第iii行中，点(i,j)(i, j)(i,j)与点(i,k)(i, k)(i,k)之间是否存在一条水平线段
column[i][j][k]表示第iii列中，点(j,i)(j, i)(j,i)与点(k,i)(k, i)(k,i)之间是否存在一条垂直线段

实际上，本题只需要记录相邻点之间的线段。但为了方便判断更大边长的正方形，可以采用动态规划的思想，将连续线段的信息合并。

2. 线段信息预处理

输入中的每条线段H i j表示第iii行连接(i,j)(i, j)(i,j)与(i,j+1)(i, j+1)(i,j+1)；V i j表示第jjj行连接(j,i)(j, i)(j,i)与(j+1,i)(j+1, i)(j+1,i)。将这些相邻点的线段标记为111。

接着进行扩展：对于任意i<ji < ji<j，如果从iii到j−1j-1j−1的线段存在，且从j−1j-1j−1到jjj的线段也存在，则合并为从iii到jjj的连续线段。这样，row[k][i][j] = 1就表示第kkk行中，从列iii到列jjj的所有相邻点之间都有水平线段。垂直线段同理。

3. 正方形判定

对于边长为kkk的正方形，其左上角顶点位于(i,j)(i, j)(i,j)（1≤i≤n−k,1≤j≤n−k1 \leq i \leq n-k, 1 \leq j \leq n-k1≤i≤n−k,1≤j≤n−k）。需要满足四条边都存在：

上边：第iii行，从列jjj到列j+kj+kj+k有水平线段，即row[i][j][j+k]
下边：第i+ki+ki+k行，从列jjj到列j+kj+kj+k有水平线段，即row[i+k][j][j+k]
左边：第jjj列，从行iii到行i+ki+ki+k有垂直线段，即column[j][i][i+k]
右边：第j+kj+kj+k列，从行iii到行i+ki+ki+k有垂直线段，即column[j+k][i][i+k]

若四条边均存在，则计数加111。

4. 输出格式

每组数据输出Problem #k，后面空一行。然后按边长从小到大输出正方形数量。若没有正方形，输出No completed squares can be found.。不同组数据之间输出一行******************************，且前后各有一个空行。

代码实现

// Squares// UVa ID: 201// Verdict: Accepted// Submission Date: 2016-03-23// UVa Run Time: 0.022s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;introw[10][10][10];// row[i][j][k]: 第 i 行中，点 (i,j) 到 (i,k) 是否有连续水平线段intcolumn[10][10][10];// column[i][j][k]: 第 i 列中，点 (j,i) 到 (k,i) 是否有连续垂直线段intn;// 网格每行/每列的点数intmain(){cin.tie(0);cout.sync_with_stdio(false);charline;// 线段类型：'H' 或 'V'intm,start,end;// m 为线段数量，start 和 end 为坐标intcounter=0;// 记录当前是第几个问题boolprintAsterisks=false;// 控制是否打印分隔符while(cin>>n){// 如果不是第一组数据，则输出分隔符（前后各有一个空行）if(printAsterisks){cout<<"\n";cout<<"**********************************\n";cout<<"\n";}if(printAsterisks==false)printAsterisks=true;counter++;// 初始化线段数组memset(row,0,sizeof(row));memset(column,0,sizeof(column));cin>>m;while(m--){cin>>line>>start>>end;if(line=='H')// 水平线段：第 start 行，连接列 end 和 end+1row[start][end][end+1]=1;else// 垂直线段：第 start 列，连接行 end 和 end+1column[start][end][end+1]=1;}// 预处理：合并连续的线段，得到任意两点间是否连续连通// 例如：第 k 行中，若从 i 到 j-1 有线段，且从 j-1 到 j 有线段，则从 i 到 j 有线段for(intk=1;k<=n;k++)for(inti=1;i<=n-2;i++)for(intj=i+2;j<=n;j++){if(row[k][i][j-1]&&row[k][j-1][j])row[k][i][j]=1;if(column[k][i][j-1]&&column[k][j-1][j])column[k][i][j]=1;}// 输出问题标题，UVa 格式要求后面空一行cout<<"Problem #"<<counter<<"\n";cout<<endl;booloutputed=false;// 标记是否有输出任何正方形// 枚举边长 k，从 1 到 n-1for(intk=1;k<=n-1;k++){inttotal=0;// 枚举左上角顶点 (i, j)for(inti=1;i<=n-k;i++)for(intj=1;j<=n-k;j++)// 判断正方形的四条边是否都存在if(row[i][j][j+k]&&row[i+k][j][j+k]&&column[j][i][i+k]&&column[j+k][i][i+k])total++;if(total>0){cout<<total<<" square (s) of size "<<k<<"\n";outputed=true;}}// 如果没有找到任何正方形，输出提示信息if(outputed==false)cout<<"No completed squares can be found."<<"\n";}return0;}