c++迷宫地图和路径
时间: 2023-11-27 11:52:29 浏览: 54
实现迷宫地图和路径可以使用深度优先搜索(DFS)或广度优先搜索(BFS)算法。
1. 深度优先搜索算法:
深度优先搜索算法使用递归的方式进行,可以通过栈来模拟。具体步骤如下:
(1)从起点开始,将其设置为已访问并入栈。
(2)判断当前位置是否为终点,如果是则返回。
(3)如果不是,则遍历其周围的点,如果该点未被访问过,将其标记为已访问并入栈,递归访问该点。
(4)如果周围的点都被访问过或者没有可访问的点,则将该点出栈,并返回上一层。
(5)重复以上步骤,直到找到终点或者栈为空。
2. 广度优先搜索算法:
广度优先搜索算法使用队列的方式进行,具体步骤如下:
(1)从起点开始,将其设置为已访问并入队。
(2)从队列中取出一个节点,遍历其周围的点,如果该点未被访问过,将其标记为已访问并入队。
(3)重复以上步骤,直到找到终点或者队列为空。
(4)如果找到终点,则回溯路径,从终点开始,依次向前找到起点。
下面是一个简单的C++代码实现:
```cpp
#include <iostream>
#include <queue>
using namespace std;
const int N = 100;
int n, m;
char g[N][N];
bool st[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; //四个方向
void dfs(int x, int y) //深度优先搜索
{
if (g[x][y] == 'G')
{
cout << "找到终点!" << endl;
return;
}
st[x][y] = true;
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] != '#' && !st[nx][ny])
{
dfs(nx, ny);
}
}
}
void bfs(int sx, int sy) //广度优先搜索
{
queue<pair<int, int>> q;
q.push({sx, sy});
st[sx][sy] = true;
while (q.size())
{
auto t = q.front();
q.pop();
int x = t.first, y = t.second;
if (g[x][y] == 'G')
{
cout << "找到终点!" << endl;
return;
}
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] != '#' && !st[nx][ny])
{
q.push({nx, ny});
st[nx][ny] = true;
}
}
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> g[i];
int sx, sy;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (g[i][j] == 'S')
{
sx = i, sy = j;
break;
}
cout << "深度优先搜索:" << endl;
dfs(sx, sy);
memset(st, 0, sizeof st); //重置st数组
cout << "广度优先搜索:" << endl;
bfs(sx, sy);
return 0;
}
```
其中,输入格式为首先输入迷宫的行数和列数,然后输入迷宫地图,其中S表示起点,G表示终点,#表示障碍物。输出格式为找到终点则输出“找到终点!”。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)
![](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)