UVA 11464 - Even Matrix：首行確定全矩陣的奇偶推理

問題描述

給定 n×n 0/1 矩陣（n ≤ 18），操作：選一格翻轉（0↔1），其上下左右四鄰格同時翻轉。求最少操作次數使全矩陣變為 0。多解輸出任意一個。

核心洞見：首行狀態決定一切

• 對第 1 行，我們可以任意選擇翻轉與否（共 2ⁿ 種枚舉）
• 對第 i (i≥2) 行，為使第 i-1 行最終為 0，第 i 行的翻轉狀態被唯一決定：若第 i-1 行第 j 列當前為 1，則必須翻轉 (i,j)
• 逐行推導至第 n 行，最後檢查第 n 行是否全 0。若是，得到一組合法解
• 枚舉所有首行狀態，取操作數最小者

狀態壓縮優化

• 每行用 int 位掩碼表示，翻轉操作為異或
• 預計算每行對上下行的影響掩碼，位運算極快

關鍵代碼邏輯

int solve(int firstRowMask) {
    memcpy(b, a, sizeof(a));
    int ops = 0;
    // 應用首行操作
    for (int j = 0; j < n; ++j)
        if (firstRowMask & (1<