UVA-10908 Largest Squares 解題紀錄

🔗 UVA-10908 Largest Squares

tags: 暴力法(Brute Force) 二分搜尋(Binary Search) 模擬(Simulation)

範例程式碼已於UVA、瘋狂程設(CPE)、ZeroJudge 上皆測試通過。

題意

給定一個二維字元矩陣，每個位置上的字元為大寫英文字母。

給定 $Q$ 個詢問，每個詢問給定一個座標 $(x, y)$，請找出該點為中心的最大正方形邊長，該正方形內的所有字元必須相同。

約束條件

• $1 \leq T \leq 20$ ，$T$ 為測試案例數。
• $1 \leq M, N \leq 100$
• $1 \leq Q \leq 20$

思路：模擬(Simulation)

方法一：暴力法(Brute Force) / 二分搜尋(Binary Search)

由於測試案例中的範圍不大，可以直接暴力法搜尋。

對於每個詢問，從半徑 $r = 1$ 開始，每次搜尋所有半徑 $< r$ 的正方形是否符合條件，若符合則更新半徑 $r$。

這裡使用了 二分搜尋(Binary Search) 來加速搜尋過程，也可以拿掉二分搜尋的部分，直接暴力法搜尋。

複雜度分析

• 時間複雜度：$\mathcal{O}(Q \cdot n^2 \cdot \log n)$ ，其中 $n = \min(M, N)$
  • 若不使用二分搜尋，則時間複雜度為 $\mathcal{O}(Q \cdot n^3)$
• 空間複雜度：$\mathcal{O}(M \cdot N)$

PythonC++

T = int(input())

def check(x, y, r):
    if x < 0 or x >= M or y < 0 or y >= N:
        return False
    for i in range(-r, r + 1):
        for j in range(-r, r + 1):
            if x + i < 0 or x + i >= M or y + j < 0 or y + j >= N:
                return False
            if mp[x + i][y + j] != mp[x][y]:
                return False
    return True

for _ in range(T):
    M, N, Q = map(int, input().split())
    mp = [list(input()) for _ in range(M)]
    print(M, N, Q)
    for _ in range(Q):
        qx, qy = map(int, input().split())
        left, right = 0, min(M, N)
        while left <= right:
            mid = (left + right) // 2
            if check(qx, qy, mid):
                left = mid + 1
            else:
                right = mid - 1
        print(2 * right + 1)

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

bool check(vector<string> &mp, int x, int y, int r) {
    int M = mp.size(), N = mp[0].size();
    if (x < 0 || x >= M || y < 0 || y >= N) return false;
    for (int i = -r; i <= r; i++) {
        for (int j = -r; j <= r; j++) {
            if (x + i < 0 || x + i >= M || y + j < 0 || y + j >= N)
                return false;
            if (mp[x + i][y + j] != mp[x][y]) return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t, m, n, q, x, y, l, r;
    cin >> t;
    while (t--) {
        cin >> m >> n >> q;
        vector<string> mp(m);
        for (int i = 0; i < m; i++) {
            cin >> mp[i];
        }
        cout << m << " " << n << " " << q << endl;
        while (q--) {
            cin >> x >> y;
            l = 0, r = min(m, n);
            while (l <= r) {
                int mid = (l + r) / 2;
                if (check(mp, x, y, mid)) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            cout << 2 * r + 1 << endl;
        }
    }
    return 0;
}

方法二：只擴散邊緣的格子

可以發現，雖然暴力法的寫法比較直觀，但是其中會有很多重複的檢查。

在檢查時，只需要檢查半徑 恰好 為 $r$ 的邊緣格子是否符合條件即可。因此可以將暴力法中 $r^2$ 的兩層迴圈，改成兩個 $r \times 2$ 的兩層迴圈。

複雜度分析

• 時間複雜度：$\mathcal{O}(Q \cdot n^2)$ ，其中 $n = \min(M, N)$ ，對於每次詢問，最多只會檢查 $O(n^2)$ 個格子。
• 空間複雜度：$\mathcal{O}(M \cdot N)$

PythonC++

T = int(input())

def check(x, y, r):
    if x < 0 or x >= M or y < 0 or y >= N:
        return False
    for i in range(-r, r + 1):
        for j in [-r, r]:
            if x + i < 0 or x + i >= M or y + j < 0 or y + j >= N:
                return False
            if mp[x + i][y + j] != mp[x][y]:
                return False
    for j in range(-r, r + 1):
        for i in [-r, r]:
            if x + i < 0 or x + i >= M or y + j < 0 or y + j >= N:
                return False
            if mp[x + i][y + j] != mp[x][y]:
                return False
    return True

for _ in range(T):
    M, N, Q = map(int, input().split())
    mp = [list(input()) for _ in range(M)]
    print(M, N, Q)
    for _ in range(Q):
        x, y = map(int, input().split())
        r = 1
        while check(x, y, r):
            r += 1
        print(2 * r - 1)

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

vector<string> mp;

bool check(int x, int y, int r) {
    int M = mp.size(), N = mp[0].size();
    if (x < 0 || x >= M || y < 0 || y >= N) return false;
    for (int i = -r; i <= r; i++) {
        for (int j = -r; j <= r; j += 2 * r) {
            if (x + i < 0 || x + i >= M || y + j < 0 || y + j >= N)
                return false;
            if (mp[x + i][y + j] != mp[x][y]) return false;
        }
    }
    for (int j = -r; j <= r; j++) {
        for (int i = -r; i <= r; i += 2 * r) {
            if (x + i < 0 || x + i >= M || y + j < 0 || y + j >= N)
                return false;
            if (mp[x + i][y + j] != mp[x][y]) return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t, m, n, q, x, y, r;
    cin >> t;
    while (t--) {
        cin >> m >> n >> q;
        mp.resize(m);
        for (int i = 0; i < m; i++) cin >> mp[i];
        cout << m << " " << n << " " << q << endl;
        while (q--) {
            cin >> x >> y;
            r = 1;
            while (check(x, y, r)) r++;
            cout << 2 * r - 1 << endl;
        }
    }
    return 0;
}

---

寫在最後

Cover photo is remixed from @Tiffany, thanks for their work!