用C++编程,使用深度优先算法解决农夫过河问题
时间: 2024-05-01 10:16:06 浏览: 22
农夫过河问题是一个经典的搜索问题,可以使用深度优先算法进行解决。以下是使用C++实现的代码:
```c++
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 6;
int cow[MAXN+1]; // 农夫和4只牛的状态,0表示在左岸,1表示在右岸
vector<int> path; // 记录路径
bool vis[MAXN+1][MAXN+1][MAXN+1][MAXN+1]; // 标记已访问状态
// 判断是否合法状态
bool check(int x1, int y1, int x2, int y2) {
if (x1 < 0 || x1 > 1 || y1 < 0 || y1 > 1 || x2 < 0 || x2 > 1 || y2 < 0 || y2 > 1) return false; // 状态值不为0或1
if ((x1 == 0 && y1 == 0) || (x2 == 0 && y2 == 0)) return false; // 农夫不在左岸
if (x1 == y1 && x2 == y2) return false; // 牛互相攻击
if ((x1 == x2 && y1 == y2) || (x1 == y2 && y1 == x2)) return false; // 农夫和牛在同一岸
return true;
}
// 深度优先搜索
bool dfs(int f1, int c1, int c2, int c3, int c4) {
if (c1 == 1 && c2 == 1 && c3 == 1 && c4 == 1) { // 找到一组可行解
for (int i = 0; i < path.size(); i++) {
cout << path[i] << " ";
}
cout << endl;
return true;
}
if (vis[f1][c1][c2][c3][c4]) return false; // 已访问过
vis[f1][c1][c2][c3][c4] = true;
if (f1 == 0) { // 农夫在左岸
if (check(1, c1, 1, c2)) { // 带一只牛过河
path.push_back(1);
if (dfs(1, 1-c1, 1, c2, c3, c4)) return true;
path.pop_back();
}
if (check(1, c1, 1, c3)) { // 带二只牛过河
path.push_back(2);
if (dfs(1, 1-c1, 1, c2, c3, c4)) return true;
path.pop_back();
}
if (check(1, c1, 1, c4)) { // 带三只牛过河
path.push_back(3);
if (dfs(1, 1-c1, 1, c2, c3, c4)) return true;
path.pop_back();
}
if (check(1, c1, 0, c1)) { // 单独过河
path.push_back(4);
if (dfs(1, 1-c1, 0, c1, c2, c3, c4)) return true;
path.pop_back();
}
} else { // 农夫在右岸
if (check(0, c1, 0, c2)) { // 带一只牛过河
path.push_back(-1);
if (dfs(0, 1-c1, 0, c2, c3, c4)) return true;
path.pop_back();
}
if (check(0, c2, 0, c3)) { // 带二只牛过河
path.push_back(-2);
if (dfs(0, 1-c2, 0, c1, c3, c4)) return true;
path.pop_back();
}
if (check(0, c3, 0, c4)) { // 带三只牛过河
path.push_back(-3);
if (dfs(0, 1-c3, 0, c1, c2, c4)) return true;
path.pop_back();
}
if (check(0, c1, 1, c1)) { // 单独过河
path.push_back(-4);
if (dfs(0, 1-c1, 1, c1, c2, c3, c4)) return true;
path.pop_back();
}
}
return false;
}
int main() {
memset(vis, false, sizeof(vis));
memset(cow, 0, sizeof(cow));
dfs(0, cow[1], cow[2], cow[3], cow[4]);
return 0;
}
```
在上述代码中,`check()`函数用于判断当前状态是否合法,`dfs()`函数则是深度优先搜索的主函数。在搜索过程中,使用`vis`数组记录已经访问过的状态,`path`数组记录搜索路径,以便输出最终的解。最后,在`main()`函数中进行初始化,并调用`dfs()`函数进行搜索。
注意,由于牛的数量较少,本题可以直接使用暴力枚举的方式进行搜索,因此不需要使用剪枝等优化策略。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)