深度优先和广度优先遍历建立一个5×5的迷宫(bool二维数组),并输出坐标
时间: 2024-02-11 19:09:31 浏览: 26
好的,我已经了解了您的需求。以下是一个使用深度优先和广度优先遍历算法生成的5x5的迷宫(使用bool类型的二维数组表示):
```
#include <iostream>
#include <stack>
#include <queue>
#include <ctime>
#include <cstdlib>
using namespace std;
const int MAXSIZE = 5;
bool maze[MAXSIZE][MAXSIZE];
bool visited[MAXSIZE][MAXSIZE];
struct Point {
int x, y;
Point(int x, int y) : x(x), y(y) {}
};
void generateMaze() {
srand(time(NULL));
int startX = rand() % MAXSIZE;
int startY = rand() % MAXSIZE;
stack<Point> s;
s.push(Point(startX, startY));
visited[startX][startY] = true;
while (!s.empty()) {
Point curr = s.top();
s.pop();
int x = curr.x;
int y = curr.y;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int randIndex = rand() % 4;
for (int i = 0; i < 4; i++) {
int newx = x + dir[randIndex][0];
int newy = y + dir[randIndex][1];
if (newx < 0 || newx >= MAXSIZE || newy < 0 || newy >= MAXSIZE || visited[newx][newy])
continue;
visited[newx][newy] = true;
maze[x + (newx - x) / 2][y + (newy - y) / 2] = true;
s.push(Point(newx, newy));
x = newx;
y = newy;
randIndex = rand() % 4;
}
}
}
void bfs() {
queue<Point> q;
q.push(Point(0, 0));
visited[0][0] = true;
while (!q.empty()) {
Point curr = q.front();
q.pop();
int x = curr.x;
int y = curr.y;
cout << "(" << x << ", " << y << ")" << endl;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int i = 0; i < 4; i++) {
int newx = x + dir[i][0];
int newy = y + dir[i][1];
if (newx < 0 || newx >= MAXSIZE || newy < 0 || newy >= MAXSIZE || visited[newx][newy] || !maze[x + (newx - x) / 2][y + (newy - y) / 2])
continue;
visited[newx][newy] = true;
q.push(Point(newx, newy));
}
}
}
void dfs(int x, int y) {
visited[x][y] = true;
cout << "(" << x << ", " << y << ")" << endl;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int i = 0; i < 4; i++) {
int newx = x + dir[i][0];
int newy = y + dir[i][1];
if (newx < 0 || newx >= MAXSIZE || newy < 0 || newy >= MAXSIZE || visited[newx][newy] || !maze[x + (newx - x) / 2][y + (newy - y) / 2])
continue;
dfs(newx, newy);
}
}
int main() {
generateMaze();
cout << "BFS:" << endl;
bfs();
cout << endl;
memset(visited, false, sizeof(visited));
cout << "DFS:" << endl;
dfs(0, 0);
return 0;
}
```
在这个代码中,我们使用了深度优先遍历和广度优先遍历算法来遍历迷宫。其中,深度优先遍历使用了递归实现,广度优先遍历使用了队列实现。在生成迷宫的过程中,我们使用了随机算法来随机选择下一个要拓展的方向。最终,程序会输出所有的坐标。