习题4-2 UVA201 Squares （34行AC代码）

紫书刷题进行中，题解系列点这里

习题4-2 UVA201 Squares （34行AC代码）

题目大意

给定n*n个点和m条边构成的图形，问该图形中含各类长度的正方形个数。

思路分析

最朴素的思想，枚举所有可能的正方形长度l，再枚举所有可能的正方形左上角坐标，依次判断，时间复杂度为O(n^3），伪代码如下：

for l~[1,n]: // 正方形边长[1,n]
	for i~[1,n-l]: // 正方形左上角坐标范围
		for j~[1,n-l]:
			判断左上角(i,j)能否构成正方形

已知左上角便可轻易推出其余三角，因此如何根据已知4顶点判断能否构成正方形成为关键，两种思路：

• 暴力遍历：每次都遍历4顶点构成的4条边，查看是否两两间连通，显然效率太低
• 最长距离：计算每个点向右/下可达到的最长距离。但左上角为(i,j)时，仅需判断左上角的向右和向下，右上角向下，左下角向右的最长距离是否大于等于l即可。时间复杂度O(n^2)，查询O(1)。

算法设计

• 定义二维数组int h[10][10]={0}, v[10][10]={0} ，分别存储水平和垂直连线关系
• 定义二维数组int right[10][10]={0}, down[10][10]={0}分别存储当前点向右和向下所能到达最远距离
• 定义一维数组int num[10]={0} 记录每种长度正方形个数，其中num[0]=0表示无符合的正方形
• 其中向右和向下所能到达最远距离，可如下计算

对于每一行，从右数第二个点向左遍历，若当前点到右侧点无连线，当前点置0；否则为右侧点个数+1

对于每一列，从下数第二个点向上遍历，若当前点到下侧点无连线，当前点置0,；否则为下侧点个数+1

for (int i = 1; i <= n; i ++) { // 每一行列
    for (int j = n-1; j >= 1; j --) { // 从右侧/下侧数第二个开始
        right[i][j] = (h[i][j] == j+1) ? right[i][j+1]+1 : 0; // 行：左->右
        down[j][i] = (v[j][i] == j+1) ? down[j+1][i]+1 : 0; // 列：上->下
    }
}

AC代码（C++11，最长距离/前缀和）

#include<bits/stdc++.h>
using namespace std;
int n, m, cnt = 0, a, b;
char ch;
int main() {
    while (cin >>n >>m) {
        int h[10][10]={0}, v[10][10]={0}; // 存储水平和垂直连线
        while (m --) { // 输入
            cin >>ch >>a >>b;
            if (ch == 'H') h[a][b] = b+1;
            else v[b][a] = b+1; // 注意顺序
        }
        int right[10][10]={0}, down[10][10]={0}, num[10]={0}; // 向右/下最远可达距离，每种长度正方形计数
        for (int i = 1; i <= n; i ++) { // 每一行列
            for (int j = n-1; j >= 1; j --) {
                right[i][j] = (h[i][j] == j+1) ? right[i][j+1]+1 : 0; // 行：左->右
                down[j][i] = (v[j][i] == j+1) ? down[j+1][i]+1 : 0; // 列：上->下
            }
        }
        for (int l = 1; l <= n; l ++) { // 遍历每个正方形长度：l:[1,n]
            for (int i = 1; i <= n - l; i ++) { // x:[1,n-l]
                for (int j = 1; j <= n - l; j ++) { // y:[1,n-l]
                    if (right[i][j] >= l && down[i][j] >= l && down[i][j+l] >= l && right[i+l][j] >= l) num[l] ++, num[0] = 1; // num[0]标记存在解
                }
            }
        }
        if (cnt != 0) printf("\n**********************************\n\n"); // 以下为输出
        printf("Problem #%d\n\n", ++cnt);
        for (int i = 1; i <= n; i ++) 
            if (num[i] != 0) printf("%d square (s) of size %d\n", num[i], i);
        if (num[0] == 0) printf("No completed squares can be found.\n");
    }
    return 0;
}

紫书刷题进行中，题解系列点这里