您可以输入任何大小的迷宫数据,使用非递归方法(堆栈或队列)来找到从迷宫外的路径,并输出路径;代码
时间: 2023-03-30 12:03:07 浏览: 101
当然可以,我可以使用深度优先搜索或广度优先搜索算法来解决这个问题。以下是使用广度优先搜索算法的代码示例:
```
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int MAXN = 100;
const int dx[4] = {, , 1, -1};
const int dy[4] = {1, -1, , };
int n, m;
char maze[MAXN][MAXN];
bool vis[MAXN][MAXN];
int pre[MAXN][MAXN];
struct Node {
int x, y;
};
bool isValid(int x, int y) {
return x >= && x < n && y >= && y < m && maze[x][y] != '#' && !vis[x][y];
}
void bfs(int sx, int sy, int ex, int ey) {
queue<Node> q;
q.push({sx, sy});
vis[sx][sy] = true;
while (!q.empty()) {
Node cur = q.front();
q.pop();
if (cur.x == ex && cur.y == ey) {
vector<Node> path;
while (cur.x != sx || cur.y != sy) {
path.push_back(cur);
cur = {pre[cur.x][cur.y] / m, pre[cur.x][cur.y] % m};
}
path.push_back({sx, sy});
reverse(path.begin(), path.end());
for (auto node : path) {
cout << "(" << node.x << ", " << node.y << ") ";
}
cout << endl;
return;
}
for (int i = ; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (isValid(nx, ny)) {
vis[nx][ny] = true;
pre[nx][ny] = cur.x * m + cur.y;
q.push({nx, ny});
}
}
}
cout << "No path found!" << endl;
}
int main() {
cin >> n >> m;
for (int i = ; i < n; i++) {
for (int j = ; j < m; j++) {
cin >> maze[i][j];
}
}
int sx, sy, ex, ey;
cin >> sx >> sy >> ex >> ey;
bfs(sx, sy, ex, ey);
return ;
}
```
这个程序可以读入迷宫的大小和数据,以及起点和终点的坐标,然后使用广度优先搜索算法来找到从起点到终点的路径,并输出路径。
阅读全文