UVa 1603 Matchsticks：火柴棒正方形消除 - IDA* + 位運算優化

題目描述

給定 n×n 火柴棒方格陣（2n(n+1) ≤ 60 根火柴），部分火柴已移除。問最少再移除多少根火柴，使圖中不存在任何完整正方形（任意大小）。

解題思路：迭代加深 A* (IDA*) + 位掩碼

1. 狀態表示：uint64_t 位掩碼，每位代表一根火柴是否存在（1 存在，0 移除）。總火柴 ≤ 60，恰好放入 64 位。
2. 預計算所有正方形：枚舉所有可能大小 (1~n) 和位置的正方形，計算其 4 條邊對應的火柴位掩碼，存入 squares[]。
3. 啟發式函數 h(s)：當前狀態 s 下仍完整的正方形數。具有單調性：移除一根火柴最多破壞 1 個正方形（實際上可破壞多個，但 h(s') ≥ h(s) - 1），滿足 IDA* 剪枝條件。
4. IDA* 搜索：從初始狀態開始，深度限制 bound = h(initial) 遞增。每步選擇一根能破壞至少一個正方形的火柴移除（優先破壞較多正方形的火柴），遞歸搜索，直到 h == 0。
5. 優化剪枝：
   • 連通分量下界：將正方形建圖（共邊連邊），每連通分量至少需移除 1 根火柴。
   • 火柴破壞力排序：優先嘗試破壞正方形數最多的火柴。

關鍵代碼框架

using ULL = unsigned long long;
ULL squares[100]; // 每個正方形的火柴掩碼
int sqCnt;
ULL initState;    // 初始火柴掩碼

int heuristic(ULL s) {
    int cnt = 0;
    for (int i = 0; i < sqCnt; ++i)
        if ((s & squares[i]) == squares[i]) ++cnt; // 正方形完整
    return cnt;
}

bool dfs(ULL s, int depth, int bound) {
    int h = heuristic(s);
    if (h == 0) return true;
    if (depth + h > bound) return false; // f = g + h > bound
    // 選擇一根火柴移除：優先能破壞最多正方形的
    // ... 遍歷火柴位，嘗試 s ^ (1ULL<