【图的深度优先遍历搜索】Fire Net

【问题描述】

   假设我们有一个方形的城市，其街道都是直的。在方形地图上，有n行和n列，每个代表一条街道或一堵墙。每个碉堡有4个射击孔，分别正对东西南北方向。在每个射击孔配备一架高射机枪。

  我们假设，子弹是如此强大，它的射程可以任意远，并能摧毁它所击中的碉堡。墙也是很坚固的，足以阻止子弹的摧毁。

  问题的目标是，在该城市中布置尽可能多的碉堡，而碉堡之间又不会相互摧毁。合理布置碉堡的原则是，没有两个碉堡在同一个水平方向或垂直方向，除非它们之间有墙相隔。在本题中，假定城市很小（最多4×4），而且有子弹不能贯穿的墙壁。 

下图为碉堡配置实例：

【算法分析】 

由于题目规模很小（n≤4），采用深度优先算法即可。

（1）数据定义，读取数据

char cMap[5][5];	//地图
int iBest;		//最优解
int n;			//地图的大小数据读取：
while(scanf("%d", &n) && n)
{	for(int i = 0; i < n; i++)cin>>cMap[i];……
}

（2）判断每个单元格能否放置碉堡

假设n=4,变量k表示单元格的序号，左上角为0，然后从左到右，从上到下。

当k＝16（n的平方）时，就表示计算结束。

变量current表示在当前布置下，所获得的能够合法布置碉堡的最大值。

对每一个单元格，可以放置碉堡（假定是合法的），也可以不放置碉堡，因此就有很多种方案。

对所有方案， current的最大值iBest，就是本题的答案。

显然当n很大时，这种搜索方法是很耗时的。

// 放置碉堡的深度优先搜索算法
//回溯算法，子集树
void solve(int k, int current)
{　　int x, y;if(k == n*n) 　　//整个地图判断完毕{　　//更新最优解if(current > iBest){iBest = current; return;}}else{　//将单元数转换为xy坐标x = k / n;y = k % n;if(cMap[x][y] == ‘.’  &&  CanPut(x, y))	//左子树{cMap[x][y] = 'O';　　　	//放置一个碉堡solve(k + 1, current + 1);cMap[x][y] = ‘.’; 		//恢复现场}solve(k + 1, current);　		//不放置碉堡，右子树}
}

(3)判断该单元格能否配置碉堡

//判断在行row和列col处能否配置碉堡
bool CanPut(int row,  int col)
{　　int i;//判断col列上的合法性for(i = row - 1; i >= 0; i--){if(cMap[i][col] == 'O') return false;if(cMap[i][col] == 'X') break;}//判断row行上的合法性for(i = col - 1; i >= 0; i--){if(cMap[row][i] == 'O') return false;if(cMap[row][i] == 'X') break;}return true;
}

【代码的完整实现】

#include<bitsdc++.h>
#define N 100
typedef long long ll;
using namespace std;
int cMap[5][5];//地图
int iBest;//最优解
int n;//地图的大小
//回溯算法，子集数
//判断在行row和列col处能否配置碉堡
bool CanPut(int row,int col)
{int i;//判断col列上的合法性for(i=row-1;i>=0;i--){if(cMap[i][col]=='o')return false;if(cMap[i][col]=='X')break;}//判断row行上的合法性for(i=col-1;i>=0;i--){if(cMap[row][i]=='o')return false;if(cMap[row][i]=='X')break;}return true;
}
void solve(int k,int current)
{int x,y;if(k==n*n)//整个地图判断完毕{//更新最优解if(current>iBest){iBest=current;return;}}else{//将单元转化为x，y坐标x=k/n;y=k%n;if(cMap[x][y]='.'&&CanPut(x,y))//左子树{cMap[x][y]='o';//放置一个碉堡solve(k+1,current+1);cMap[x][y]='.';//恢复现场}solve(k+1,current);//不放置碉堡，右子树}
}
int main()
{cin>>n;for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>cMap[i][j];}}solve(1,1);cout<<iBest;
}