如果只是想簡單地對整個程式做計算統計，通常使用UNIX下的time命令就足夠了。由於我用的是Mac系統，和Linux系統的輸出可能有不同，不過關鍵都是這三個時間：user: 運行用戶態代碼所花費的時間，也即CPU實際用於執行該進程的時間，其他進程和進程阻塞的時間不計入此數字；system: 在內核中... ...
下麵繼續通過幾個示例體會二進位枚舉方法的應用。
【例1】建造碉堡
問題描述
設有一個街道筆直的方形城市。該城市的地圖是一個有n行和n列的正方形，每行代表一條街道或一堵牆。
碉堡是一座有四個開口的小城堡，可以通過這些開口射擊。四個開口分別面向北、東、南和西。每個開口都會有一支機槍射擊。
假設一顆子彈威力巨大，它可以穿越任何距離，併在途中摧毀一座碉堡。另一方面，一堵牆是如此堅固，可以阻擋子彈。
你的目標是在該城市中建造儘可能多的碉堡，建造的碉堡要求任意兩座碉堡都不會互相摧毀。也就是說沒有兩個碉堡位於同一水平行或垂直列上，除非至少有一堵牆將它們隔開。
例如，圖1（a）是沒有建造碉堡的初始初始狀態（圖中正方形黑塊代表牆）；圖1（b）和（c）是建造可行方案（圖中黑色實心圓代表建造的碉堡），圖1（d）和（e）是建造不可行的方案。對圖1（a）所示的城市狀態，最多可以建造5座碉堡。圖1（b）給出了一種可行的建造方案，當然還有其他幾種建造方案。
你的任務是編寫一個程式，在給定地圖描述的情況下，計算可以在城市中滿足要求建造的碉堡的最大數量。
輸入
輸入包括多組測試用例。每組測試用例以包含正整數n的行開始，n是城市的大小，n最多為4。接下來的n行字元串分別描述地圖的一行，其中字元“.”表示開放空間，大寫字母“X”表示牆。輸入字元串中沒有空格。n=0，表示輸入結束。
輸出
對於每個測試用例，輸出一行，其中包含可以在城市中滿足要求建造的碉堡的最大數量。
輸入樣例
4
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
4
....
....
....
....
0
輸出樣例
5
1
5
4
（1）編程思路。
由於題目中n不大於4，地圖中最多16個位置。因此，可以採用二進位枚舉的方法，枚舉在這n*n個位置中任選若幹個位置建造碉堡的各種組合情況，然後對每個組合情況，逐個判斷該組合情況中所建造的每個碉堡的可行性。
（2）源程式。
#include <stdio.h> #include <string.h> int n; char a[5][5]; int dir[4][2] = {1,0,0,1,-1,0,0,-1}; int judge(int x) // 判斷計算二進位數表示的狀態x中的1位是否都能建造碉堡，如不能返回1；否則返回可建造的碉堡個數 { char b[5][5]; int c[20], tot = 0; // 分別保存碉堡建造的位置和總個數 memcpy(b, a, sizeof(a)); int i,j; for (i = 0; i < n * n; i++) // 在二進位狀態x中的1位建造碉堡 { if (x & (1 << i)) { int xx = i / n; int yy = i % n; if (b[xx][yy] == 'X') // 剪枝，如果碉堡建造在牆上，直接返回-1 return -1; b[xx][yy] = 'a'; // 建造碉堡 c[tot++] = i; } } for (i = 0; i < tot; i++) // 看建造的每個碉堡是否可行 { int x1 = c[i] / n; int y1 = c[i] % n; for (j = 0; j < 4; j++) // 四個方向遍歷 { int x2 = x1 + dir[j][0]; int y2 = y1 + dir[j][1]; while(x2 >= 0 && x2 < n && y2 >= 0 && y2 < n)// 控制邊界 { if(b[x2][y2] == 'X') break; // 碰到牆跳出迴圈 if(b[x2][y2] == 'a') return -1; // 碰到另一個碉堡'a'，不可行 x2 += dir[j][0]; // 繼續往這方向遍歷 y2 += dir[j][1]; } } } return tot; } int main() { while(scanf("%d",&n) && n!=0) { int ans = 0; int i; for (i = 0; i < n; i++) scanf("%s",a[i]); for (i = 0; i < (1 << (n * n)); i++) // 二進位枚舉地圖各點建造碉堡的全部組合 { int cnt=judge(i); if (cnt>ans) ans = cnt; } printf("%d\n",ans); } return 0; }
將上面的源程式提交給HDU題庫 HDU 1045 Fire Net （http://acm.hdu.edu.cn/showproblem.php?pid=1045），可以Accepted。
【例2】子圖像
問題描述
如果可以從圖像B中刪除一些行和一些列的像素，生成的圖像與圖像A相同，則稱圖像A是圖像B的子圖像。圖2所示的圖像A是圖像B的子圖像，因為從圖像B中移除中間一行和中間一列的像素後，所產生的圖像與A相同。
給定兩個黑白圖像A和B，確定A是否是B的子圖像。
輸入
輸入第一行包含兩個整數r和c（1≤ r、c≤ 20），表示圖像A的行數和列數。以下r行，每行包含一個長度為c的字元串，給出一個r×c的0-1矩陣，表示圖像A的像素。下一行包含兩個整數R和C（r≤ R≤ 20，c≤ C≤ 20），表示圖像B的行數和列數。以下R行，每行包含一個長度為C的字元串，給出一個代表圖像B像素的R×C的0-1矩陣。0表示白色像素；1表示黑色像素。
輸出
如果圖像A是圖像B的子圖像，則輸出“Yes”；否則，輸出“No”。
輸入樣例
2 2
11
10
3 3
101
000
100
輸出樣例
Yes
（1）編程思路。
可以通過在圖像B對應的0-1矩陣中尋找是否存在圖像A所對應的0-1矩陣來判斷圖像A是否是圖像B的子圖像。
具體做法是：用二進位枚舉矩陣B中R行的組合，若枚舉的二進位數中1的個數正好為矩陣a的行數r，則表示可以在矩陣B的R行中選出矩陣A的r行。這種情況下，再用迴圈窮舉的方法，看矩陣B的C列中，是否可以選出c列，矩陣B選中的r行在這c列上的值與矩陣A的值一致。
（2）源程式。
#include <stdio.h> int main() { char a[21][21],b[21][21]; int na,ma,nb,mb; scanf("%d%d",&na,&ma); int i,j,k; for (i=0; i<na; i++) scanf("%s",a[i]); scanf("%d%d",&nb,&mb); for (i=0; i<nb; i++) scanf("%s",b[i]); int flag=0,h[21]; for (k=0; k<(1<<nb); k++) // 二進位枚舉B矩陣的行組合 { int cnt=0; for (j =0; j<nb; j++) // 遍歷二進位的每一位 { if (k & (1 << j)) // 判斷二進位第j位是否為1，若為1，表示行選中 h[cnt++]=j; // 如果第j個元素選中，則記錄選中的行號 } if (cnt==na) // 矩陣B選中的行數正好是矩陣A的行數na { int st=0; // 矩陣B中可以挑選的起始列號 while (st<=mb-ma) { int cola=0,ff=1; for (i=st; i<mb; i++) // 從矩陣B的起始列到最後列中看能否找到矩陣A的所有列 { ff=1; for (j=0; j<na; j++) // 矩陣A中各行的當前列在矩陣B選中行的某列是否一致 if(a[j][cola]!=b[h[j]][i]) { ff=0; break; } if (ff) cola++; if (cola==ma) break; // A矩陣的ma列全部可在B矩陣中找到 } if (cola==ma) // A矩陣的ma列全部可在B矩陣中找到 { flag=1; break; } st++; // 當前起始列不恰當，將下一列作為起始列，重新找 } if (flag==1) break; // 已找到答案，退出迴圈 } } if (flag) printf("Yes\n"); else printf("No\n"); return 0; }
將上面的源程式提交給北大POJ題庫 POJ 3600 Subimage Recognition （http://poj.org/problem?id=3600），可以Accepted。
【例3】查找0-1矩陣
問題描述
給定一個M×N的0-1矩陣，你能找到一些讓每個列包含且僅包含一個1的行嗎。
輸入
輸入包括多組測試用例。每組測試用例的第一行輸入為M，N（M≤ 16，N≤ 300)，接下來的M行每行包含N個用空格分隔的整數0或1。
輸出
對於每個測試用例，如果你能找到它，輸出“Yes, I found it”，否則輸出“It is impossible”。
輸入樣例
3 3
0 1 0
0 0 1
1 0 0
4 4
0 0 0 1
1 0 0 0
1 1 0 1
0 1 0 0
輸出樣例
Yes, I found it
It is impossible
（1）編程思路。
本題同樣採用二進位枚舉各行的組合，再用位運算來判斷所選的那些行是否滿足每列只有一個1。
由於題目中給出最多16行，因此可以用一個int型整數（32位>16）的每個二進位位來表示每列狀態。以輸入樣例中的4×4矩陣來說明。第0列4行上的數字分別為0、1、1、0，對應二進位數為110，將其對應的十進位整數6保存到數組元素col[0]中，第1列4行上的數字分別為0、0、1、1，對應二進位數為1100，將其對應的十進位整數12保存到數組元素col[1]中；同理，col[2]=0，col[3]=5。
同樣，對應輸入樣例中的3×3矩陣，則有 col[0]=4，col[1]=1，col[2]=2。
當二進位枚舉到狀態i時，要判斷所選行中，第j列是否有且只有1個1。可以令t = col[j]&i，這樣就把枚舉的行裡面的1取了出來。因為在枚舉的二進位狀態i中，選中的行相應位為1，未選中的行相應位為0，而 0 & 1=0，這樣某列在未選中行上的1均會變成0。
得到t值後，如果t=0，說明枚舉的這些行對應的某列裡面一個1都不含，肯定不滿足要求。如果 t != 0，再看 t&（t-1)的值，若該值等於0，表示 t 只有一個1，也就是在所選行中，第j列有且只有1個1；否則，t中不止1個1，不滿足要求。
（2）源程式。
#include <stdio.h> #include <string.h> int main() { int m,n; while (scanf("%d%d", &m, &n)!=EOF){ int col[301]; int i,j,x,flag = 0; memset(col, 0, sizeof(col)); for (i=0; i<m; i ++){ // 輸入時預處理，將每列中各行0、1組成的二進位數轉換為十進位數保存到數組col中 for (j=0; j<n; j++){ scanf("%d",&x); if (x==1) col[j] += (1 << i); if (i==m-1 && col[j]==0) flag = 1; // 若每列1的個數為0，顯然不可能 } } if (flag){ printf("It is impossible\n"); continue; } for (i=1; i<(1<<m); i++){ // 用二進位枚舉，對各行的組合進行選擇 for (j = 0; j < n; j ++){ int t = col[j] & i; if (t==0 || (t & (t-1))) { break; } } if (j==n) {flag = 1; break; } } if (flag == 0) printf("It is impossible\n"); else printf("Yes, I found it\n"); } return 0; }
將上面的源程式提交給北大POJ題庫 POJ 3740 Easy Finding（http://poj.org/problem?id=3740），可以Accepted。
