一、普通枚舉

顧名思義，就是把所有情況全部羅列出來，然后找到符合題目要求的那一個，因此它是一種純暴力的算法。

一般情況下，枚舉策略都是會超時的。此時要先根據題目的數據范圍來判斷暴力枚舉是否可以通過。 如果不行的話，就要考慮用其他各種算法來進行優化（比如?分，雙指針，前綴和與差分等）。

使用枚舉策略時，重點思考枚舉的對象（枚舉什么），枚舉的順序（正序還是逆序），以及枚舉的方式（普通枚舉？?進制枚舉？遞歸枚舉？）。

1. 鋪地毯

【題目鏈接】

[P1003 NOIP 2011 提高組] 鋪地毯 - 洛谷

【題目描述】

為了準備一個獨特的頒獎典禮，組織者在會場的一片矩形區域（可看做是平面直角坐標系的第一象限）鋪上一些矩形地毯。一共有 $n$ 張地毯，編號從 $1$ 到 $n$。現在將這些地毯按照編號從小到大的順序平行于坐標軸先后鋪設，后鋪的地毯覆蓋在前面已經鋪好的地毯之上。

地毯鋪設完成后，組織者想知道覆蓋地面某個點的最上面的那張地毯的編號。注意：在矩形地毯邊界和四個頂點上的點也算被地毯覆蓋。

【輸入格式】

輸入共 $n+2$ 行。

第一行，一個整數 $n$，表示總共有 $n$ 張地毯。

接下來的 $n$ 行中，第 $i+1$ 行表示編號 $i$ 的地毯的信息，包含四個整數 $a,b,g,k$，每兩個整數之間用一個空格隔開，分別表示鋪設地毯的左下角的坐標 $(a,b)$ 以及地毯在 $x$ 軸和 $y$ 軸方向的長度。

第 $n+2$ 行包含兩個整數 $x$ 和 $y$，表示所求的地面的點的坐標 $(x,y)$。

【輸出格式】

輸出共 $1$ 行，一個整數，表示所求的地毯的編號；若此處沒有被地毯覆蓋則輸出 -1。

【示例一】

輸入

3
1 0 2 3
0 2 3 3
2 1 3 3
2 2

輸出

3

【示例二】

輸入

3
1 0 2 3
0 2 3 3
2 1 3 3
4 5

輸出

-1

【說明/提示】

【樣例解釋 1】

如下圖，$1$ 號地毯用實線表示，$2$ 號地毯用虛線表示，$3$ 號用雙實線表示，覆蓋點 $(2,2)$ 的最上面一張地毯是 $3$ 號地毯。

【數據范圍】

對于 $30\%$ 的數據，有 $n\le 2$。
對于 $50\%$ 的數據，$0\le a,b,g,k\le 100$。
對于 $100\%$ 的數據，有 $0\le n\le 10^4$, $0\le a,b,g,k\le {10}^5$。

noip2011 提高組 day1 第 $1$ 題。

---

(1) 解題思路

枚舉每一個地毯，判斷該該點是否被這個地毯覆蓋。注意枚舉的時候最好逆序枚舉。因為我們需要找的是最上面的地毯，如果順序枚舉的話那么必須要枚舉完所有情況才能找到最上面的地毯，而逆序枚舉的話所找到第一個覆蓋的地毯一定是最上面的地毯。

在判斷一個點是否被一個地毯覆蓋的時候只需要用到簡單的數學知識即可。假設地毯左下角點的坐標為 (a, b)，由題意，這張地毯的右上角點的坐標為 (a + g, b + k)。那么如果一個點 (x, y) 被覆蓋，一定有 a <= x <= a + g 且 b <= y <= b + k。

---

(2) 代碼實現

#include<iostream>using namespace std;const int N = 1e4 + 10;
int a[N], b[N], g[N], k[N];
int n, x, y;// 尋找最上面的地毯并返回其下標，沒找到返回-1
int find()
{for(int i = n; i >= 1; --i)  // 逆序枚舉每一個地毯{if(x >= a[i] && x <= a[i] + g[i]&& y >= b[i] && y <= b[i] + k[i]){return i;}}return -1;
}int main()
{cin >> n;for(int i = 1; i <= n; ++i)cin >> a[i] >> b[i] >> g[i] >> k[i];cin >> x >> y;cout << find();return 0;
}

---

2. 回文日期

【題目鏈接】

[P2010 NOIP 2016 普及組] 回文日期 - 洛谷

【題目描述】

在日常生活中，通過年、月、日這三個要素可以表示出一個唯一確定的日期。

牛牛習慣用 $8$ 位數字表示一個日期，其中，前 $4$ 位代表年份，接下來 $2$ 位代表月份，最后 $2$ 位代表日期。顯然：一個日期只有一種表示方法，而兩個不同的日期的表 示方法不會相同。

牛牛認為，一個日期是回文的，當且僅當表示這個日期的 $8$ 位數字是回文的。現在，牛牛想知道：在他指定的兩個日期之間（包含這兩個日期本身），有多少個真實存在的日期是回文的。

一個 $8$ 位數字是回文的，當且僅當對于所有的 $i$（$1\le i\le 8$）從左向右數的第 $i$ 個數字和第 $9?i$ 個數字（即從右向左數的第 $i$ 個數字）是相同的。

例如：

• 對于 2016 年 11 月 19 日，用 $8$ 位數字 $20161119$ 表示，它不是回文的。
• 對于 2010 年 1 月 2 日，用 $8$ 位數字 $20100102$ 表示，它是回文的。
• 對于 2010 年 10 月 2 日，用 $8$ 位數字 $20101002$ 表示，它不是回文的。

每一年中都有 $12$ 個月份：

其中，$1,3,5,7,8,10,12$ 月每個月有 $31$ 天；$4,6,9,11$ 月每個月有 $30$ 天；而對于 $2$ 月，閏年時有 $29$ 天，平年時有 $28$ 天。

一個年份是閏年當且僅當它滿足下列兩種情況其中的一種：

1. 這個年份是 $4$ 的整數倍，但不是 $100$ 的整數倍；
2. 這個年份是 $400$ 的整數倍。

例如：

• 以下幾個年份都是閏年：$2000,2012,2016$。
• 以下幾個年份是平年：$1900,2011,2014$。

【輸入格式】

兩行，每行包括一個 $8$ 位數字。

第一行表示牛牛指定的起始日期。

第二行表示牛牛指定的終止日期。

保證 ${date}_1$ 和 ${date}_2$ 都是真實存在的日期，且年份部分一定為 $4$ 位數字，且首位數字不為 $0$。

保證 ${date}_1$ 一定不晚于 ${date}_2$。

【輸出格式】

一個整數，表示在 ${date}_1$ 和 ${date}_2$ 之間，有多少個日期是回文的。

【示例一】

輸入

20110101
20111231

輸出

1

【示例二】

輸入

20000101
20101231

輸出

2

【說明/提示】

【樣例說明】

對于樣例 1，符合條件的日期是 $20111102$。

對于樣例 2，符合條件的日期是 $20011002$ 和 $20100102$。

【子任務】

對于 $60\%$ 的數據，滿足 ${date}_1={date}_2$。

---

(1) 解題思路

• 思路一：暴力枚舉

最容易想到的，就是設置一個變量 cnt 記錄回文日期的個數，枚舉兩個日期中間的所有數字，判斷是否是回文日期，如果是，那么判斷是否是一個合法的日期，如果合法那么 cnt++。

• 思路二：枚舉年份

在暴力枚舉的過程中，我們實際上枚舉了很多沒有用的數字。通過觀察可以發現，如果一個日期數字的前四位（也就是年份）確定了的話，那么它的后四位也就隨之確定了。比如 $2010$，想要構成回文日期的話那么它的后四位必定是 $0102$。因此我們僅需枚舉前四位（年份）再加判斷是否合法即可。

• 思路三：枚舉月日

枚舉年份的情況有可能還是太多了，我們可以只枚舉月日，即枚舉后四位，那么年份也就確定了。而在這種情況下我們僅需最多枚舉 365 / 366 種情況，將日月組成的數字倒過來拼成年份的數字，最終將組成的回文日期與題目給的日期作比較判斷是否在題目給定的范圍之內即可，大大減少了時間復雜度。

---

(2) 代碼實現

#include<iostream>using namespace std;int date1, date2;
int day[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int main()
{cin >> date1 >> date2;int cnt = 0;for(int i = 1; i <= 12; i++){for(int j = 1; j <= day[i]; j++){int y = (j % 10) * 1000 + (j / 10) * 100 + (i % 10) * 10 + (i / 10);  // 倒過來拼成年份int num = y * 10000 + i * 100 + j;  // 拼成回文日期if(date1 <= num && num <= date2) cnt++;  // 判斷是否在題目給定的范圍內}}cout << cnt;return 0;
}

---

3. 掃雷

【題目鏈接】

[P2327 SCOI2005] 掃雷 - 洛谷

【題目描述】

相信大家都玩過掃雷的游戲。那是在一個 $n\times m$ 的矩陣里面有一些雷，要你根據一些信息找出雷來。萬圣節到了，“余”人國流行起了一種簡單的掃雷游戲，這個游戲規則和掃雷一樣，如果某個格子沒有雷，那么它里面的數字表示和它 $8$ 連通的格子里面雷的數目。現在棋盤是 $n\times 2$ 的，第一列里面某些格子是雷，而第二列沒有雷，如下圖：

由于第一列的雷可能有多種方案滿足第二列的數的限制，你的任務即根據第二列的信息確定第一列雷有多少種擺放方案。

【輸入格式】

第一行為 $N$，第二行有 $N$ 個數，依次為第二列的格子中的數。（$1\le N\le 10000$）

【輸出格式】

一個數，即第一列中雷的擺放方案數。

【示例一】

輸入

2
1  1

輸出

2

---

(2) 解題思路

通過觀察可以發現，當我們確定第一列第一個位置是否有雷時，那么第一列雷的排列情況也就全部確定了。所以，我們僅需枚舉出第一列第一個位置放或不放地雷兩種情況，然后檢查這兩種情況下的地雷分布是否合法。

具體來說，我們可以用兩個數組 a[N] 和 b[N] 來保存第一列地雷分布情況（0 表示無地雷，1 表示有地雷）和第二列的數字。那么第一列的第 i 個位置是否有地雷就可以這樣計算：a[i] = b[i - 1] - a[i - 2] - a[i - 1]，如果 a[i] 小于 0 或大于 1，說明這種情況不合法，即不存在這種情況。

還需要注意兩個細節問題：

1. 兩數組的下標可以從 1 開始計數，因為當第一個位置確定之后我們是從第二個位置開始枚舉的，如果從下標為 0 開始計數則對應 a[1]，計算時的 a[i - 2] 會發生越界的情況。所以從下標為 1 開始計數可以有效避免這種情況。

2. 如果一共有 n 個數，那么循環遍歷要遍歷到下標 n + 1 處，當 a[n + 1] 不為 0 的時候，同樣也是不合法的情況。比如當第二列是數字 1, 3 時，實際上是不合法的，這個時候我們可以通過計算 a[3] 的位置是否為 0 來判斷。

---

(2) 代碼實現

#include<iostream>using namespace std;const int N = 1e4 + 10;
int a[N], b[N];
int n;int check1()
{a[1] = 0;for(int i = 2; i <= n + 1; i++){a[i] = b[i - 1] - a[i - 1] - a[i - 2];if(a[i] < 0 || a[i] > 1) return 0;  // 不合法的情況}if(a[n + 1] == 0) return 1;else return 0;  // n + 1 位置不為 0 也是不合法的
}int check2()
{a[1] = 1;for(int i = 2; i <= n + 1; i++){a[i] = b[i - 1] - a[i - 1] - a[i - 2];if(a[i] < 0 || a[i] > 1) return 0;}if(a[n + 1] == 0) return 1;else return 0;
}int main()
{cin >> n;for(int i = 1; i <= n; i++) cin >> b[i];int ans = 0;ans += check1();  // a[1] 不放地雷ans += check2();  // a[1] 放地雷cout << ans;return 0;
}

---

二、二進制枚舉

二進制枚舉：用一個數二進制表示中的 0/1 表示兩種狀態，從而達到枚舉各種情況。

注：利用二進制枚舉時，會用到?些位運算的知識。

多說無益，直接實戰！

---

1. 子集

【題目鏈接】

78. 子集 - 力扣（LeetCode）

【題目描述】

給你?個整數數組 nums ，數組中的元素互不相同。返回該數組所有可能的?集（冪集）。 解集不能包含重復的?集。你可以按任意順序返回解集。

【示例一】

輸?

nums = [1,2,3] 

輸出

[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

---

(1) 解題思路

可以發現，數組 nums 中的數字都有選或不選兩種情況，那么我們可以用 0 和 1 分別來表示不選和選這兩種狀態。通過二進制的方式來枚舉出所有的子集。并且含有 n 個數的集合，其子集一共有 2 ^ n 個，即 1 << n 個。

于是，當我們有了一個二進制數比如 101 時，表示第 1，3 位要放到子集中，形成 [1, 3]。那么如何用代碼實現對應位的取舍呢？我們可以用一個變量 i 遍歷二進制的每一位，如果第 i 位為 1，那么表示取，那么對應的 nums[i] 就存放在一個子集中。

判斷第 i 位是否為 1：(對應的二進制數 >> i) & 1。

原理就是把這個二進制數的第 i 位移到最低位，然后和 1 進行按位與操作，如果這個位是 1，那么結果就是 1，否則為 0。

十進制	二進制	子集	判斷取舍（用 i 遍歷二進制的每一位）
0	000	[]	所有位為 0，都不取
1	001	[1]	i = 0: 001 >> 0 &1 = 1 (取)
2	010	[2]	i = 1: 010 >> 1 &1 = 1 (取)
3	011	[1,2]	i = 0, 1 為真
4	100	[3]	i = 2: 100 >> 2 &1 = 1 (取)
5	101	[1,3]	i = 0, 2 為真
6	110	[2,3]	i = 1, 2 為真
7	111	[1,2,3]	所有位為真，都取

---

(2) 代碼實現

class Solution 
{
public:vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> ret;int n = nums.size();for(int st = 0; st < (1 << n); st++)  // 枚舉 0~(2^n - 1){vector<int> tmp;  // 存儲子集for(int i = 0; i < n; i++){// 如果 st 對應的二進制的第 i 位為 1，那么就放進子集中if((st >> i) & 1) tmp.push_back(nums[i]);}ret.push_back(tmp);}return ret;}
};

---

2. 費解的開關

【題目鏈接】

P10449 費解的開關 - 洛谷

【題目描述】

你玩過“拉燈”游戲嗎？

$25$ 盞燈排成一個 $5\times 5$ 的方形。

每一個燈都有一個開關，游戲者可以改變它的狀態。

每一步，游戲者可以改變某一個燈的狀態。

游戲者改變一個燈的狀態會產生連鎖反應：和這個燈上下左右相鄰的燈也要相應地改變其狀態。

我們用數字 $1$ 表示一盞開著的燈，用數字 $0$ 表示關著的燈。

下面這種狀態

10111
01101
10111
10000
11011

在改變了最左上角的燈的狀態后將變成：

01111
11101
10111
10000
11011

再改變它正中間的燈后狀態將變成：

01111
11001
11001
10100
11011

給定一些游戲的初始狀態，編寫程序判斷游戲者是否可能在 $6$ 步以內使所有的燈都變亮。

【輸入格式】

第一行輸入正整數 $n$，代表數據中共有 $n$ 個待解決的游戲初始狀態。

以下若干行數據分為 $n$ 組，每組數據有 $5$ 行，每行 $5$ 個字符。

每組數據描述了一個游戲的初始狀態。

各組數據間用一個空行分隔。

【輸出格式】

一共輸出 $n$ 行數據，每行有一個小于等于 $6$ 的整數，它表示對于輸入數據中對應的游戲狀態最少需要幾步才能使所有燈變亮。

對于某一個游戲初始狀態，若 $6$ 步以內無法使所有燈變亮，則輸出 -1。

【示例一】

輸入

3
00111
01011
10001
11010
1110011101
11101
11110
11111
1111101111
11111
11111
11111
11111

輸出

3
2
-1

【說明/提示】

測試數據滿足 $0<n\le 500$。

---

(1) 解題思路

通過思考我們可以發現，按燈這樣的操作具有以下三點 性質：

• 每一盞燈，最多只會按一次

這是因為一盞燈只有開或者關兩個狀態，所以當一盞燈被按兩次的時候，與它不被按的情況是等價的；被按三次的時候，與它被按一次是等價的，以此類推。

• 按燈的先后順序，不會影響最終的結果

• 第一行的按法確定了之后，后續燈的按法就跟著確定了

因為當第一行按了以后，假如說變成 00101，那么第二行只能去按第1, 2, 4 個位置才能使第一行的三個 0 變成 1，后面第三行和第四行是影響不到第一行的狀態的。所以第一行確定了，那么其余行也就確定了。

---

有了這三點性質之后，我們就可以確定我們的解題思路了：

1. 枚舉出第一行的按法。（由于燈只有 1 和 0 兩種狀態，因此使用二進制枚舉）
2. 根據第一行的按法，計算出第一行和第二行被按之后的新狀態。
3. 根據第一行的結果，推導出第二行的按法，第三、四、五行同理。
4. 按完最后一行，判斷所有燈是否全亮。

---

• 如何枚舉出第一行所有的按法？

由于每一行有五盞燈，所以二進制枚舉的時候只需從 00000 枚舉到 11111（$2^5?1$）即可。0 代表這個位置不按，1 代表按。

• 對于一個二進制數（按法），如何計算出有多少個 1（按了多少次）？

只需下面的方式即可：

// 計算二進制數中 1 的個數
int calc(int x)
{ int cnt = 0;while(x){cnt++;x &= x - 1;}return cnt;
}

可以在草稿紙上試一下，按位與幾次就會拿掉幾個 1。

• 如何存儲燈的初始狀態？

我們可以用二進制來存儲每一行的燈的開關狀態，比如第一行的燈是 00110，那么我們只需要在一個一維數組中的第一位存儲一個 00110 這個二進制數即可。

這里還有一個小技巧，就是我們可以把 1 轉化成 0，0 轉化成 1，這樣反過來存儲，問題就變成了把燈全部變成 0 要多少步，這樣的話，當我們判斷是否是全滅的時候，僅需看最后一行對應存儲的值是否為 0 即可。當然這樣轉化還有其他好處，一會兒會提到。

• 如何根據一個按燈方式 push，計算出當前行 a[i] 以及下一行 a[i + 1] 被按之后的狀態？

對于 a[i] 行來說，我們可以用位運算快速計算得到。對于一行燈的狀態 a[i] 如 10111，給定一種按燈方式 push 如 00100，我們僅需使用 a[i] = a[i] ^ push ^ (push << 1) ^ (push >> 1) 就可以讓對應位置及其左右兩邊的燈的狀態改變，因為 1、0 這兩個數異或 1 就可以實現 1 變 0，0 變 1。

但是這里有一個小小的問題的，就是 push << 1 可能會讓第 5 位變成 1，這是一個非法的位置，可能會影響后續的判斷，因此我們需要截斷高位。這個時候只需讓計算后的 a[i] 按位與上 111110 即可，即 (1 << 5) - 1。

所以計算 a[i] 的公式為：a[i] = a[i] ^ push ^ (push << 1) ^ (push >> 1) & ((1 << n) - 1))。

計算第 a[i + 1] 行就比較簡單了，只需要修改 push 中對應為 1 的位置，不需要管左右，易得 a[i + 1] = a[i + 1] ^ push。

• 如何求下一行怎么按？

我們的問題已經轉化成了變成全滅，因此我們的 a[i + 1] 的需要按的位置只能是上一行 a[i] 亮著的位置，恰好就是 a[i]，即 next_push = a[i]。這也是將問題轉化成全滅的好處之一。

---

(2) 代碼實現

#include<iostream>
#include<cstring>using namespace std;const int N = 10;
int n = 5;
int a[N];  // 存儲每一行燈的狀態
int t[N];  // a數組的備份// 計算一個二進制數中有多少個 1
int calc(int x)
{int cnt = 0;while(x){cnt++;x &= (x - 1);}return cnt;
}int main()
{int T; cin >> T;while(T--){// 有多組測試用例時記得清空上一輪的數據memset(a, 0, sizeof(a));// 讀入數據for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){char ch; cin >> ch;// 正常情況下應該是: if(ch == '1') a[i] |= 1 << j;// 現在我們反著來存if(ch == '0') a[i] |= 1 << j;}}int ans = 0x3f3f3f3f;  // 記錄最終需要的最小操作數// 二進制枚舉出第一行每一種情況for(int st = 0; st < (1 << n); st++){memcpy(t, a, sizeof(a));int push = st;  // 當前情況下的按法int cnt = 0;  // 當前情況下所需的最小操作數// 從上到下按每一行for(int i = 0; i < n; i++){cnt += calc(push);  // 計算每一行按了多少次t[i] = t[i] ^ push ^ (push << 1) ^ (push >> 1);  // 計算當前行按之后的狀態t[i] &= (1 << n) - 1;  // 清除影響t[i + 1] ^= push;  // 計算下一行按之后的狀態push = t[i];  // 下一行的按法}if(t[n - 1] == 0) ans = min(ans, cnt);  // 如果能全滅，更新最小操作數}if(ans > 6) cout << -1 << endl;else cout << ans << endl;}return 0;
}

---

3. even parity

【題目鏈接】

UVA11464 Even Parity - 洛谷

【題目描述】

給你一個 $n\times n$ 的 $01$ 矩陣（每個元素非 $0$ 即 $1$），你的任務是把盡量少的 $0$ 變成 $1$，使得原矩陣便為偶數矩陣（矩陣中每個元素的上、下、左、右的元素（如果存在的話）之和均為偶數）。

【輸入格式】

輸入的第一行為數據組數 $T$（$T\le 30$）。每組數據：第一行為正整數 $n$（$1\le n\le 15$）；接下來的 $n$ 行每行包含 $n$ 個非 $0$ 即 $1$ 的整數，相鄰整數間用一個空格隔開。

【輸出格式】

對于每組數據，輸出被改變的元素的最小個數。如果無解，輸出 $?1$。

【示例一】

輸入

3
3
0 0 0
0 0 0
0 0 0
3
0 0 0
1 0 0
0 0 0
3
1 1 1
1 1 1
0 0 0

輸出

Case 1: 0
Case 2: 3
Case 3: -1

---

(1) 解題思路

這道題與上一道題很相似，我們也可以發現當我們把第一行的改變情況確定了之后，那么后面的改變狀態也隨之確定。因此，還是可以枚舉第一行所有的改變情況。

• 如何枚舉出第一行所有的按法？

同上道題一樣，我們從 0 枚舉到 (1 << n) - 1。但是需要注意的是，不是所有的情況都是合法的，因為這道題只能從 0 變成 1，因此我們還需要判斷每一行的最終情況是否合法。如果都是 0 變 1，則合法，計數；如果不合法，跳出本次循環，枚舉下一個狀態。

• 如何根據一個改變方式 change，計算出下一行 a[i + 1] 的狀態？

如果一個 a[i] 的某一個位置被改變后，我們需要計算 a[i + 1] 對應的位置，也就是 a[i] 的正下方，需要這個位置的上下左右數字之和為偶數，也就是上下左右的 0 的個數為偶數或者 1 的個數為偶數。由異或的性質可知，這個位置的上下左右的異或結果為 0，求下方的數實際上就是上左右三個數的異或結果。所以有 a[i + 1] = a[i - 1] ^ (a[i] << 1) ^ (a[i] >> 1)。

---

(2) 代碼實現

#include<iostream>
#include<cstring>using namespace std;const int N = 20;
int n;
int a[N];
int t[N];int calc(int x, int y)  // t[i], change
{int sum = 0;for(int j = 0; j < n; j++){// 如果 t[i] 的第 j 位是 1 而 change 的第 j 位是 0 則不合法，返回-1if(((x >> j) & 1) == 1 && ((y >> j) & 1) == 0) return -1;// 如果 t[i] 的第 j 位是 0 而 change 的第 j 位是 1 則合法，并統計一次次數if(((x >> j) & 1) == 0 && ((y >> j) & 1) == 1) sum++;}return sum;
}int solve()
{int ret = 0x3f3f3f3f;  // 記錄最終所需的最小操作數// 枚舉第一行的所有改變情況for(int st = 0; st < (1 << n); st++){memcpy(t, a, sizeof(a));int change = st;  // 每一行的改變情況int cnt = 0;  // 記錄當前情況下的最小操作數bool flag = true;for(int i = 1; i <= n; i++){int c = calc(t[i], change);  // 判斷是否合法,若合法則計算操作次數if(c == -1)  // 如果不合法{flag = false;break;}// 如果合法cnt += c;  // 統計改變次數t[i] = change;  // 當前行的最終狀態change = t[i - 1] ^ (t[i] >> 1) ^ (t[i] << 1);  // 下一行的狀態change &= (1 << n) - 1;  // 清除影響}if(flag) ret = min(ret, cnt);}if(ret == 0x3f3f3f3f) return -1;else return ret;
}int main()
{int T; cin >> T;for(int k = 1; k <= T; k++){memset(a, 0, sizeof(a));cin >> n;// 用二進制來讀入數據for(int i = 1; i <= n; i++){for(int j = 0; j < n; j++){int x; cin >> x;if(x) a[i] |= 1 << j;}}printf("Case %d: %d\n", k, solve());}return 0;
}