UVA 11134 Fabled Rooks：二維棋子放置拆解為一維貪心區間調度

問題描述

N×N 棋盤，需放置 N 個車（Rook），互不攻擊（即每行每列最多一個）。每個車有限制區域：左上角 (x1,y1) 到右下角 (x2,y2)。求任意合法放置方案或判定不可能。

核心洞察：維度分解

車的攻擊約束：行衝突 ↔ x 坐標衝突；列衝突 ↔ y 坐標衝突。行列約束完全獨立！

問題分解為兩個完全相同的一維問題：

1. X 維：N 個區間 [x1, x2]，選 N 個互不相同的整數點
2. Y 維：N 個區間 [y1, y2]，選 N 個互不相同的整數點

兩維各自有解 ⇔ 原問題有解。合併對應索引即得最終坐標。

一維區間選點貪心策略

經典「區間調度 / 区间选点」問題：

• 按區間右端點 升序 排序
• 依次處理每個區間，選擇區間內 最小的未被佔用點
• 若某區間無可用點 → 無解

證明：右端點最小的區間「選擇自由度」最低，優先安排最優。

完整代碼實現

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 5005;
struct Interval {
    int l, r, id, pos;
    bool operator<(const Interval& o) const {
        if (r != o.r) return r < o.r;  // 右端點優先
        return l < o.l;
    }
} ix[MAXN], iy[MAXN];

int n, vis[MAXN], ansX[MAXN], ansY[MAXN];

bool solve1D(Interval* a) {
    sort(a, a + n);
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < n; ++i) {
        bool ok = false;
        for (int p = a[i].l; p <= a[i].r; ++p) {
            if (!vis[p]) {
                vis[p] = 1;
                a[i].pos = p;
                ok = true;
                break;
            }
        }
        if (!ok) return false;
    }
    // 按原 id 排序輸出
    sort(a, a + n, [](const Interval& a, const Interval& b) { return a.id < b.id; });
    return true;
}

int main() {
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; ++i) {
            scanf("%d%d%d%d", &ix[i].l, &iy[i].l, &ix[i].r, &iy[i].r);
            ix[i].id = iy[i].id = i;
        }
        bool ok = solve1D(ix) && solve1D(iy);
        if (!ok) {
            puts("IMPOSSIBLE");
        } else {
            for (int i = 0; i < n; ++i)
                printf("%d %d\n", ix[i].pos, iy[i].pos);
        }
    }
    return 0;
}

關鍵細節

1. 坐標範圍：1~n，vis 數組開 n+1 即可
2. 保持原序輸出：排序後按 id 恢復順序
3. 貪心正確性：若存在解，最早截止的區間一定能選到某個點，且選最小可用點不壞解

複雜度

• 排序：O(N log N)
• 掃描選點：O(N²) 最壞情況（每次掃描到 r），N≤5000 可接受
• 優化：用并查集「下一個可用點」可降至 O(N α(N))

并查集優化版選點

int fa[MAXN];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

bool solve1D_fast(Interval* a) {
    sort(a, a + n);
    for (int i = 1; i <= n; ++i) fa[i] = i;
    fa[n+1] = n+1;  // 哨兵
    
    for (int i = 0; i < n; ++i) {
        int p = find(a[i].l);
        if (p > a[i].r) return false;
        a[i].pos = p;
        fa[p] = find(p + 1);  // 標記 p 已用，指向下一個
    }
    sort(a, a + n, [](auto& a, auto& b) { return a.id < b.id; });
    return true;
}