传教士与野人过河问题C++实现
时间: 2023-12-10 10:03:43 浏览: 106
传教士与野人过河问题是一个经典的逻辑问题,可以利用深度优先搜索或广度优先搜索等算法来解决。下面是一份使用深度优先搜索解决传教士与野人过河问题的C++代码示例:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1e4 + 5;
const int dx[] = { 0, 0, -1, 1 };
const int dy[] = { -1, 1, 0, 0 };
int M, C; // 初始左岸传教士和野人数量
bool vis[MAXN][MAXN]; // vis[i][j]表示i个传教士、j个野人是否搜索过
bool check(int m, int c) { // 判断状态是否合法
return m >= 0 && c >= 0 && M - m >= C - c && M - m >= 0 && C - c >= 0;
}
void dfs(int m, int c) {
if (m == M && c == C) { // 到达目标状态
cout << "Success!" << endl;
return;
}
vis[m][c] = true;
for (int i = 0; i < 4; i++) { // 枚举下一步的状态
int nm = m - dx[i], nc = c - dy[i];
if (!vis[nm][nc] && check(nm, nc)) {
dfs(nm, nc);
}
}
}
int main() {
memset(vis, false, sizeof(vis));
cin >> M >> C;
dfs(M, C);
return 0;
}
```
在上述代码中,我们使用一个布尔型二维数组`vis`来记录每个状态是否已经被搜索过,以避免重复搜索。函数`check`用于判断当前状态是否合法,即当前左岸传教士和野人数量是否满足要求。在函数`dfs`中,我们首先标记当前状态已经被搜索过,然后枚举下一步可能的状态,并逐一进行递归搜索。如果到达目标状态,则输出“Success!”;否则程序将继续搜索。
阅读全文