#include <iostream> #include <stack> #include <cstdlib> #include <ctime> using namespace std; const int MAXN = 100; const char WALL = '#'; const char PATH = ' '; const char START = 'S'; const char END = 'E'; const int dx[4] = { -1, 0, 1, 0 }; const int dy[4] = { 0, 1, 0, -1 }; int n, m; char maze[MAXN][MAXN]; bool vis[MAXN][MAXN]; stack<pair<int, int>> st; void init() { // 随机生成迷宫 srand(time(NULL)); n = rand() % 10 + 5; m = rand() % 10 + 5; int sx = rand() % n; int sy = rand() % m; int ex = rand() % n; int ey = rand() % m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (i == sx && j == sy) maze[i][j] = START; else if (i == ex && j == ey) maze[i][j] = END; else if (rand() % 4 == 0) maze[i][j] = WALL; else maze[i][j] = PATH; } } } void print() { // 输出迷宫 cout << "Maze:" << endl; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cout << maze[i][j] << ' '; } cout << endl; } } bool dfs(int x, int y) { // 深度优先搜索 vis[x][y] = true; st.push(make_pair(x, y)); if (maze[x][y] == END) { return true; } for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && maze[nx][ny] != WALL && !vis[nx][ny]) { if (dfs(nx, ny)) { return true; } } } st.pop(); return false; } void solve() { // 求解迷宫 memset(vis, false, sizeof(vis)); while (!st.empty()) st.pop(); dfs(0, 0); } void print_path() { // 输出路径 cout << "Path:" << endl; while (!st.empty()) { auto p = st.top(); st.pop(); cout << '(' << p.first << ", " << p.second << ')' << endl; } } int main() { init(); print(); solve(); print_path(); return 0; } 在这个代码的基础上,添加路径不存在的情况
时间: 2024-02-01 07:03:58 浏览: 25
在代码中,我们可以在dfs函数中添加一个判断,如果搜索完所有可行的路径后,仍然没有找到终点,那么就说明路径不存在,此时返回false即可。
具体来说,我们可以在dfs函数的末尾添加一个判断:
```c++
if (st.empty()) {
cout << "Path does not exist" << endl;
return false;
}
```
完整代码如下:
```c++
#include <iostream>
#include <stack>
#include <cstdlib>
#include <ctime>
using namespace std;
const int MAXN = 100;
const char WALL = '#';
const char PATH = ' ';
const char START = 'S';
const char END = 'E';
const int dx[4] = { -1, 0, 1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
int n, m;
char maze[MAXN][MAXN];
bool vis[MAXN][MAXN];
stack<pair<int, int>> st;
void init() {
// 随机生成迷宫
srand(time(NULL));
n = rand() % 10 + 5;
m = rand() % 10 + 5;
int sx = rand() % n;
int sy = rand() % m;
int ex = rand() % n;
int ey = rand() % m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == sx && j == sy) maze[i][j] = START;
else if (i == ex && j == ey) maze[i][j] = END;
else if (rand() % 4 == 0) maze[i][j] = WALL;
else maze[i][j] = PATH;
}
}
}
void print() {
// 输出迷宫
cout << "Maze:" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << maze[i][j] << ' ';
}
cout << endl;
}
}
bool dfs(int x, int y) {
// 深度优先搜索
vis[x][y] = true;
st.push(make_pair(x, y));
if (maze[x][y] == END) {
return true;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && maze[nx][ny] != WALL && !vis[nx][ny]) {
if (dfs(nx, ny)) {
return true;
}
}
}
st.pop();
if (st.empty()) {
cout << "Path does not exist" << endl;
return false;
}
}
void solve() {
// 求解迷宫
memset(vis, false, sizeof(vis));
while (!st.empty()) st.pop();
dfs(0, 0);
}
void print_path() {
// 输出路径
cout << "Path:" << endl;
while (!st.empty()) {
auto p = st.top();
st.pop();
cout << '(' << p.first << ", " << p.second << ')' << endl;
}
}
int main() {
init();
print();
solve();
print_path();
return 0;
}
```