POJ 2495 棋盤覆蓋：兩格缺失的黑白染色判定法

題目描述

給定一個 8×8 的國際象棋棋盤，其中恰好有兩個格子被挖去。判斷能否用 1×2 的多米諾骨牌（長方形）無重疊、無超出地覆蓋剩餘所有格子。

核心洞察：黑白染色不變量

將棋盤按國際象棋方式黑白相間染色。每張 1×2 骨牌無論橫放或豎放，必覆蓋一黑一白兩個格子。因此，任何可完全覆蓋的區域，黑白格子數量必須相等。

若被挖去的兩格同色，剩餘區域黑白格數差 2，無法覆蓋；若異色，黑白格數相等，總存在覆蓋方案（此為充分必要條件，證明涉及圖論完美匹配）。

算法實現

座標 (a,b) 和 (c,d) 的顏色由 (a+b) % 2 決定。兩格同色當且僅當曼哈頓距離為偶數：

同色 ⇔ (|a-c| + |b-d|) % 2 == 0
異色 ⇔ (|a-c| + |b-d|) % 2 == 1

完整代碼

#include <cstdio>
#include <cstdlib>

int main() {
    int k, a, b, c, d;
    scanf("%d", &k);
    for (int i = 1; i <= k; ++i) {
        scanf("%d%d%d%d", &a, &b, &c, &d);
        int dist = abs(a - c) + abs(b - d);
        printf("Scenario #%d:\n%d\n\n", i, dist % 2);
    }
    return 0;
}

複雜度分析

• 時間：O(K)，K 為測試用例數
• 空間：O(1)

延伸思考

若挖去格子數超過 2，或棋盤非矩形，需使用二分圖最大匹配（如匈牙利算法、Dinic）判定是否存在完美匹配。POJ 2446 即為此類通用解法。本題利用「恰好 2 格缺失」的特殊性，將 O(V·E) 問題降維為 O(1) 數學判定，是典型的「找不變量」技巧。