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