欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Uva- 201 - Squares

程序员文章站 2022-03-30 08:24:52
...

原文地址:https://blog.qjm253.cn/?p=376

正方形(Squares, ACM/ICPC World Finals 1990, UVa201)

原题地址: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的正方形。

Uva- 201 - Squares

代码实现

#include <iostream>
#include <array>

using namespace std;
const int MAX_LEN = 10;


bool checkV(const array<array<int, 10>, 10> &arr, int i, int j) {
    return arr[i][j] >= 2;
}

bool checkH(const array<array<int, 10>, 10> &arr, int i, int j) {
    return arr[i][j] == 1 || arr[i][j] == 3;
}

/**
 * 检查以(i, j)为左上顶点是否能组成一个边长为len的正方形
 * @param arr
 * @param i
 * @param j
 * @param len
 */
bool checkBuildSquare(const array<array<int, 10>, 10> &arr, int i, int j, int len) {
    for (int s = i; s < i + len; s++) {
        if (!checkV(arr, s, j) || !checkV(arr, s, j + len))
            return false;
    }
    for (int s = j; s < j + len; s++) {
        if (!checkH(arr, i, s) || !checkH(arr, i + len, s))
            return false;
    }
    return true;
}

void check(const array<array<int, MAX_LEN>, MAX_LEN> &arr, int n) {
    static array<int, MAX_LEN> squares{};
    squares.fill(0);
    int maxLen;
    for (int i = 1; i < n; i++)
        for (int j = 1; j < n; j++) {
            if (arr[i][j] != 3)      //一个点→或者↓没有变则不会是某个正方形的左上端点
                continue;
            maxLen = min(n - i, n - j);
            for (int k = 1; k <= maxLen; k++) {
                if (checkBuildSquare(arr, i, j, k))
                    ++squares[k];
            }
        }
    bool hasSquare = false;
    for (int i = 1; i < MAX_LEN; i++) {
        if (squares[i] == 0)
            continue;
        hasSquare = true;
        cout << squares[i] << " square (s) of size " << i << endl;
    }
    if (!hasSquare) {
        cout << "No completed squares can be found." << endl;
    }
}


int main() {
    /**
     * 1 -> H
     * 2 -> V
     * 3 -> HV
     */
    array<array<int, MAX_LEN>, MAX_LEN> sides{};
    int n, sideNum;
    char c;
    unsigned int i, j;
    int tern = 0;
    bool first = true;
    while (cin >> n >> sideNum) {
        ++tern;
        if(first){
           first = false;
        } else {
            cout << endl << "**********************************" << endl << endl;
        }
        for (auto &s : sides)
            s.fill(0);
        for (int k = 0; k < sideNum; k++) {
            cin >> c >> i >> j;
            if (c == 'H')
                sides[i][j] += 1;
            else if (c == 'V')
                sides[j][i] += 2;
        }
        cout << "Problem #" << tern << endl << endl;

        check(sides, n);

    }
}