下面继续通过几个示例体会二进制枚举方法的应用。
【例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(&