图的搜索算法---8.2 ZOJ1002-Fire Net--合理布置碉堡

阳光穿透心脏的1/2处 2024-03-23 15:06 6阅读 0赞

**目录**

问题：

分析：

主要的算法代码：

完整代码：

出问题的代码：

原因：

正确代码：

代码分析：

算法函数讲解：

CanPut函数

solve函数

运行结果：

--------------------

### 问题： ###

> ¢ 假设我们有一个方形的城市，其街道都是直的。在方形地图上，有 *n* 行和 *n* 列，每个代表一条街道或一堵墙。每个碉堡有 4个射击孔，分别正对东西南北方向。在每个射击孔配备一架高射机枪。
> 
> ¢ 我们假设，子弹是如此强大，它的射程可以任意远，并能摧毁它所击中的碉堡。墙也是很坚固的，足以阻止子弹的摧毁。
> 
> ¢ 问题的目标是，在该城市中布置尽可能多的碉堡，而碉堡之间又不会相互摧毁。合理布置碉堡的原则是，没有两个碉堡在同一个水平方向或垂直方向，除非它们之间有墙相隔。在本题中，假定城市很小（最多 4 × 4），而且有子弹不能贯穿的墙壁。

![7df57b546766406e8d829ba923b99fbb.png][]

#### 分析： ####

¢ **由于** **题目规模** **很小（** ***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****）判断每个单元格能否放置碉堡**

¢ 变量 *k* 表示单元格的序号，左上角为 0 ，然后从左到右， 从上到下。

l 当 *k* ＝ 16 （ n 2 ） 时，就表示计算结束。

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

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

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

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

### 主要的算法代码： ###

/*
        算法8.1（1） 放置碉堡的深度优先搜索算法
    */
    //回溯算法，子集树
    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);　		//不放置碉堡，右子树
    　　}
    }
    
    /*
        算法8.1（2）判断在行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;
    }

> 该算法使用深度优先搜索（DFS）的思想，从地图的左上角开始，尝试在每个单元格中放置碉堡或者不放置碉堡，直到整个地图都被覆盖。在 DFS 的过程中，我们通过 `CanPut` 函数来判断当前位置能否放置碉堡，通过 `solve` 函数进行递归搜索，最后更新最优解并输出。

### 完整代码：  ###

#### 出问题的代码： ####

*  无论输入什么，结果都为0.

/*
 *	假设我们有一个方形的城市，其街道都是直的。在方形地图上，
 	有n行和n列，每个代表一条街道或一堵墙。每个碉堡有4个射击孔，
 	分别正对东西南北方向。在每个射击孔配备一架高射机枪。
 	我们假设，子弹是如此强大，它的射程可以任意远，并能摧毁它所击中的碉堡。
 	墙也是很坚固的，足以阻止子弹的摧毁。
 	问题的目标是，在该城市中布置尽可能多的碉堡，而碉堡之间又不会相互摧毁。
 	合理布置碉堡的原则是，没有两个碉堡在同一个水平方向或垂直方向，
 	除非它们之间有墙相隔。在本题中，假定城市很小（最多4×4），而且有子弹不能贯穿的墙壁。
 */
 #include<iostream>
 using namespace std;
 
 char 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{
 		//将单元数转换为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);//不放置碉堡，右子树
 	}
 }
 
 int main() {
 	while (cin >> n && n) {
 		for (int i = 0; i < n; i++) {
 			cin >> cMap[i];
 		}
 		iBest = 0;//初始化最优解为0
 		solve(0, 0);//从第一个单元格开始搜索
 		cout << iBest << "\t";//输出最优解
 		cout << endl;
 	}
 	return 0;
 }

#### 原因： ####

> 这个代码存在一些问题：
> 
> 1.  在 `CanPut` 函数中，第 5 行的循环条件错误，应该是 `i >= 0` 而不是 `i++`，否则会导致死循环。
> 2.  在 `solve` 函数中，第 17 行的判断条件使用了赋值符号 `=`，应该改为相等性判断符号 `==`。
> 3.  在 `solve` 函数中，没有对地图进行 DFS 搜索时需要恢复现场，即放置/撤回碉堡，否则会影响后续的搜索结果。在放置碉堡后递归搜索后，需要在返回时立即撤回放置的碉堡，恢复现场，使得程序能够正确地搜索到剩余的节点。
> 
> 修改后的代码如下所示：

//判断在行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{
 //将单元数转换为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);//不放置碉堡，右子树
 }
 }
 
 int main() {
 while (cin >> n && n) {
 for (int i = 0; i < n; i++) {
 cin >> cMap[i];
 }
 iBest = 0;//初始化最优解为0
 solve(0, 0);//从第一个单元格开始搜索
 cout << iBest << "\t";//输出最优解
 cout << endl;
 }
 return 0;
 }

#### 正确代码： ####

示例1-

#include<iostream>
 using namespace std;
 
 const int MAXN = 4;
 char cMap[MAXN][MAXN];//地图
 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;
 	}
 	for (i = row + 1; i < n; 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;
 	}
 	for (i = col + 1; i < n; 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 {
 		//将单元数转换为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);//不放置碉堡，右子树
 	}
 }
 
 int main() {
 	while (cin >> n && n) {
 		for (int i = 0; i < n; i++) {
 			cin >> cMap[i];
 		}
 		iBest = 0;//最优解初始化为0
 		solve(0, 0);//从第一个单元格开始搜索
 		cout << iBest << endl;//输出最优解
 	}
 	return 0;
 }

####  ####

示例2--

【针对错误修改后的】

/*
 *	假设我们有一个方形的城市，其街道都是直的。在方形地图上，
 	有n行和n列，每个代表一条街道或一堵墙。每个碉堡有4个射击孔，
 	分别正对东西南北方向。在每个射击孔配备一架高射机枪。
 	我们假设，子弹是如此强大，它的射程可以任意远，并能摧毁它所击中的碉堡。
 	墙也是很坚固的，足以阻止子弹的摧毁。
 	问题的目标是，在该城市中布置尽可能多的碉堡，而碉堡之间又不会相互摧毁。
 	合理布置碉堡的原则是，没有两个碉堡在同一个水平方向或垂直方向，
 	除非它们之间有墙相隔。在本题中，假定城市很小（最多4×4），而且有子弹不能贯穿的墙壁。
 */
 #include<iostream>
 using namespace std;
 
 char 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 {
 		//将单元数转换为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);//不放置碉堡，右子树
 	}
 }
 
 int main() {
 	while (cin >> n && n) {
 		for (int i = 0; i < n; i++) {
 			cin >> cMap[i];
 		}
 		iBest = 0;//初始化最优解为0
 		solve(0, 0);//从第一个单元格开始搜索
 		cout << iBest;//输出最优解
 		cout << endl;
 	}
 	return 0;
 }

### 代码分析： ###

> 【示例2--】这段代码实现了一个基于深度优先搜索（DFS）的算法来解决布置碉堡的问题。在地图上放置碉堡时，需要保证每个碉堡之间不能相互摧毁，即两个碉堡不能在同一行或同一列，除非它们之间被隔开的是墙。
> 
> 具体地，算法的主要思路是，采用 DFS 算法的思想，从第一个单元格开始逐个位置进行判断，如果该位置可以放置碉堡，则将其放置，并以此为基础继续向下搜索；如果该位置不能放置碉堡，则不做处理并继续向下搜索。搜索过程中需要记录当前已经放置的碉堡的数量，当所有空位都被判断完毕时，将当前数量与历史最佳数量比较，更新最佳数量即可。同时，
> 
>  在放置碉堡后，需要及时恢复现场，即撤回放置的碉堡，使得程序能够正确地搜索到剩余的节点。
> 
> 总之，该算法通过深度优先搜索实现了对于布置碉堡的问题的求解，从而找到在给定地图内布置尽可能多的碉堡的方案。

> while (cin >> n && n) \{ 
> for (int i = 0; i < n; i++) \{ 
> cin >> cMap\[i\]; 
> \} 
> iBest = 0;//初始化最优解为0 
> solve(0, 0);//从第一个单元格开始搜索 
> cout << iBest;//输出最优解 
> cout << endl; 
> \}
> 
> 这段代码使用了一个一维字符数组 `cMap` 来存储整个地图，其中 `cMap[i]` 存储第 `i` 行地图数据。例如：
> 
> **4**
> 
> **.X..**
> 
> **....**
> 
> **XX..**
> 
> **....**
> 
> `cMap[0]`就是 **.X..** ，不能有空格，就是一行字符
> 
> 在 `for` 循环中，程序逐行读入标准输入流中的字符，并将其存储到相应的 `cMap` 子数组中，从而完成了逐行读入字符来形成 `cMap` 一维字符数组这一操作。 
>

--------------------

> **实现过程解析：**
> 
> 这段代码实现了一个深度优先搜索算法，用于解决在一个n \* n大小的方形城市中布置尽可能多的碉堡，而碉堡之间又不会相互摧毁的问题。其主要思路为：
> 
> 1.  对于每个单元格，判断能否放置一个碉堡。如果可以放置，则将碉堡放置在该单元格上，并继续向下搜索；如果不能放置，则直接向下搜索。
> 2.  搜索完整个城市后，记录最优解即可。
> 
> 具体实现细节如下：
> 
> 1.  使用一个二维字符数组cMap来表示城市地图，并使用一个变量iBest来记录当前最优解。
> 2.  使用CanPut函数来判断在行row和列col处能否配置碉堡。具体实现方法为，在该单元格所在的行上搜索，从该单元格往上搜索到第一个墙壁或者碉堡，如果碰到的是碉堡，则返回false，否则继续向上搜索；在该单元格所在的列上同理。
> 3.  使用solve函数进行深度优先搜索。solve函数有两个参数，k表示当前搜索到第几个单元格，current表示当前已经放置了多少个碉堡。如果整个城市都搜索完毕，则与当前最优解比较，更新最优解；否则，将单元数转换为坐标x和y，如果当前单元格可以放置碉堡，则将碉堡放置在该单元格上，并继续向下搜索；如果不能放置，则直接向下搜索。每次递归结束后，需要将现场恢复（即将该单元格还原为初始状态）。
> 4.  在主函数中，循环读入城市地图，初始化最优解为0，并调用solve函数开始搜索。搜索完毕后，输出最优解即可。

--------------------

### 算法函数讲解： ###

#### **CanPut函数** ####

--------------------

> **CanPut函数的实现分两步。首先是判断列上的合法性，其次是判断行上的合法性:**
> 
> 1.  判断列上的合法性
> 
> 为了判断在(row, col)处能否放置一个碉堡，我们需要判断该列中是否有墙或碉堡。具体的实现为：
> 
> 从row-1向上遍历该列，如果该单元格上面有碉堡，说明不能再往上放置碉堡，返回false; 如果该单元格上面有墙，说明往上可以放置碉堡，退出循环； 如果该单元格上面没有碉堡和墙，则继续向上遍历。
> 
> 1.  判断行上的合法性
> 
> 为了判断在(row, col)处能否放置一个碉堡，我们需要判断该行中是否有墙或碉堡。具体的实现为：
> 
> 从col-1向左遍历该行，如果该单元格左边有碉堡，说明不能再往左放置碉堡，返回false; 如果该单元格左边有墙，说明往左可以放置碉堡，退出循环； 如果该单元格左边既没有碉堡也没有墙，则继续向左遍历。
> 
> 最后，如果该单元格同时满足列上和行上的要求，则说明在(row, col)处可以放置一个碉堡，返回true；否则，返回false。
> 
> 以下是CanPut函数的完整实现（C++代码）：
> 
>     bool CanPut(int row, int col) {
>         // 判断列上的合法性
>         for (int i = row - 1; i >= 0; i--) {
>             if (cMap[i][col] == 'O') {  // 该单元格上面有碉堡，不能放置
>                 return false;
>             }
>             if (cMap[i][col] == 'X') {  // 该单元格上面有墙，可以放置
>                 break;
>             }
>         }
>     
>         // 判断行上的合法性
>         for (int j = col - 1; j >= 0; j--) {
>             if (cMap[row][j] == 'O') {  // 该单元格左边有碉堡，不能放置
>                 return false;
>             }
>             if (cMap[row][j] == 'X') {  // 该单元格左边有墙，可以放置
>                 break;
>             }
>         }
>     
>         return true;
>     }
> 
> 总之，CanPut函数的实现就是为了判断在(row, col)处能否放置一个碉堡。对于每一个空白的单元格，它必须满足列上和行上都没有碉堡才能放置碉堡，否则会与已经放置的碉堡发生冲突，导致方案不可行。

--------------------

#### solve函数 ####

> solve函数是基于深度优先搜索实现的，用来放置碉堡并求解最优解。该函数的参数k表示搜索的单元格序号，current表示当前已经放置的碉堡数量。
> 
> 首先判断当前的单元格是否可以放置碉堡，如果可以，则在该位置放置碉堡，继续搜索下一个单元格进行递归操作。如果不能放置碉堡，则直接跳过该单元格，继续搜索下一个单元格进行递归操作。
> 
> 当搜索到最后一个单元格时，需要判断当前放置的碉堡数量是否是历史最优解，如果是则更新最优解。
> 
> 在递归过程中，通过回溯操作可以将状态恢复到先前的状态。当搜索完成后，返回最优解的数量。
> 
> 整个solve函数的实现，就是一个通过深度优先搜索找出符合要求的所有放置策略，然后取其中的最优策略的过程。
> 
> 总体的递归实现过程可以简述如下：
> 
> 1.  判断当前单元格能否放置碉堡
> 2.  如果可以，在该位置放置碉堡，继续搜索下一个单元格进行递归操作
> 3.  如果不能，直接跳过该单元格，继续搜索下一个单元格进行递归操作
> 4.  当搜索到最后一个单元格时，判断当前方案是否是最优解
> 5.  通过回溯操作将状态恢复到先前的状态
> 6.  返回最优解数量

--------------------

### 运行结果： ###

1--

![9414e325ae2640b7959b6a8fa52351da.png][]

2---

![638b20cb319b48fca9aea36d6dccfc27.png][]

[7df57b546766406e8d829ba923b99fbb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/a5dc41c73f5b42f8962af1e13585ee95.png
[9414e325ae2640b7959b6a8fa52351da.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/b536c2c39d0e4457a2d8017fb55aa76c.png
[638b20cb319b48fca9aea36d6dccfc27.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/44ffbd37b09d4416813a5be314e5717f.png