下面繼續通過幾個示例體會二進制列舉方法的應用，
【例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，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/538500.html
標籤：C
下一篇：每日演算法之二叉樹的下一個結點