UVA 201 Squares（數正方形）問題詳解與二維前綴和思想解法

UVA 201 Squares（數正方形）問題詳解與二維前綴和思想解法

給定n×n（2≤n≤9）點陣，部分相鄰點間有水平/垂直線段連接。統計所有由線段圍成的正方形數量，按邊長（以線段數為單位）從小到大輸出。多組數據，用例間輸出**********************************分隔。

數據結構建模

• H[i][j] = 1：第i行、第j列與j+1列之間有水平線段（1≤i≤n, 1≤j<n）。
• V[i][j] = 1：第i列、第j行與j+1行之間有垂直線段（1≤i≤n, 1≤j<n）。
• 輸入H i j對應H[i][j]=1；V i j對應V[j][i]=1（注意行列互換，統一以行、列為第一、第二索引）。

判定邊長為k的正方形

左上角頂點(x,y)（1≤x,y≤n-k），需滿足：

• 上邊：H[x][y] ... H[x][y+k-1] 全為1
• 下邊：H[x+k][y] ... H[x+k][y+k-1] 全為1
• 左邊：V[x][y] ... V[x+k-1][y] 全為1
• 右邊：V[x][y+k] ... V[x+k-1][y+k] 全為1

四條邊各k段線段，共4k段。暴力檢查每個可能左上角、每個邊長，複雜度O(n^4)，n≤9完全可行。

C++ 參考實現（AC代碼）

#include <iostream>
#include <algorithm>
using namespace std;

int H[10][10], V[10][10]; // 水平、垂直線段
int n, m;

void init() {
    for (int i=0; i<=n; ++i)
        for (int j=0; j<=n; ++j)
            H[i][j] = V[i][j] = 0;
}

void input() {
    char type; int i, j;
    for (int k=0; k<m; ++k) {
        cin >> type >> i >> j;
        if (type == 'H') H[i][j] = 1;
        else V[j][i] = 1; // V列行 -> V[行][列]
    }
}

// 檢查左上角(x,y)邊長k是否成正方形
bool checkSquare(int x, int y, int k) {
    for (int d=0; d<k; ++d) {
        if (!H[x][y+d]) return false;       // 上
        if (!H[x+k][y+d]) return false;     // 下
        if (!V[x+d][y]) return false;       // 左
        if (!V[x+d][y+k]) return false;     // 右
    }
    return true;
}

// 統計邊長k的正方形總數
int countSizeK(int k) {
    int cnt = 0;
    for (int i=1; i<=n-k; ++i)
        for (int j=1; j<=n-k; ++j)
            if (checkSquare(i, j, k)) ++cnt;
    return cnt;
}

int main() {
    int caseNo = 0;
    while (cin >> n >> m) {
        init();
        input();
        if (caseNo++) {
            cout << endl << "**********************************" << endl << endl;
        }
        cout << "Problem #" << caseNo << endl << endl;
        bool found = false;
        for (int k=1; k<n; ++k) {
            int cnt = countSizeK(k);
            if (cnt) {
                cout << cnt << " square (s) of size " << k << endl;
                found = true;
            }
        }
        if (!found) cout << "No completed squares can be found." << endl;
    }
    return 0;
}

關鍵點總結

• 坐標系統一：輸入V i j中i是列、j是行，存入V[j][i]使第一維為行、第二維為列，與H一致，邏輯清晰。
• 邊界處理：循環上界n-k確保正方形不超出點陣範圍。
• 輸出格式：用例編號、空行、分隔線、square(s)複數形式、無正方形時的特定提示，嚴格遵循題目要求。
• 複雜度：O(n^4)，n≤9極快，無需優化。

本題是網格圖形識別的入門經典，展示了如何將幾何條件轉化為數組索引檢查，以及格式化輸出的工程細節。