C语言实现走迷宫
C语言实现走迷宫是计算机科学中一个经典的问题,目的是在一个迷宫中找到从起点到终点的路径。该问题可以使用深度优先搜索(Depth-First Search,DFS)和广度优先搜索(Breadth-First Search,BFS)两种方法解决。
深度优先搜索(DFS)
深度优先搜索是一种常用的搜索算法,用于遍历图或树形结构。该算法的思想是站在入口,考虑自己下一步可以走哪里,走到下一个位置后,再考虑下一步怎么走,一直走下去,直到没有路,然后再返回最近的一个岔路口,选其它任一条没试过的路,如果不能走,再尝试其他的路,直到这个岔路口的路全部试完,再回到上一个路口,看是否能走到出口。
在C语言中,使用DFS解决走迷宫问题可以使用递归函数来实现。定义一个数组来存储迷宫的字符,然后使用一个flag变量来标记是否找到出口。接着,使用一个递归函数dfs来搜索路径,该函数将当前位置的坐标作为参数,并标记当前位置已经走过。然后,对于四个方向(上、下、左、右),如果下一个位置不为墙('*')且未被标记过,则递归调用dfs函数,直到找到出口。如果找到出口,则返回1,否则返回0.
代码实现如下:
```c
#include<bits/stdc++.h>
using namespace std;
char a[20][20]; // 存储迷宫字符数组
int flag, m, n;
int sdep_x[4] = {-1, 1, 0, 0}, sdep_y[4] = {0, 0, -1, 1}; // 控制上下左右方向
int vis[20][20]; // 标记走过的路
void dfs(int x, int y) {
vis[x][y] = 1; // 代表被标记过了
if (a[x][y] == 'T') // 找到出口
{
flag = 1;
return;
}
for (int i = 0; i < 4; i++) // 搜索路径
{
int h = x + sdep_x[i];
int l = y + sdep_y[i];
if (a[h][l] != '*' && !vis[h][l] && h >= 0 && h < n && l >= 0 && l < m) // 搜索路径的条件
{
dfs(h, l);
}
}
}
int main() {
while (cin >> n >> m) {
memset(vis, 0, sizeof(vis)); // 初始化数组
flag = 0;
int f, g;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
if (a[i][j] == 'S') // 先找到路口
{
f = i;
g = j;
}
}
dfs(f, g);
if (flag)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}
```
广度优先搜索(BFS)
广度优先搜索是一种常用的搜索算法,用于遍历图或树形结构。该算法的思想是将接下来一步的所有路都列出来,在之后的所有扩展之中,在以一个为下一步,再将所有的该步可以到达的下一步,全部列举出来,再将第二步的其他选择中的每一步,都一一做扩展,每次扩展,都要检查所扩展的地方有没有到达搜索的要求。
在C语言中,使用BFS解决走迷宫问题可以使用队列来实现。定义一个结构体来存储迷宫的坐标,然后使用一个队列来存储扩展的点。接着,使用一个循环来遍历队列,直到队列为空。如果找到出口,则返回1,否则返回0.
代码实现如下:
```c
#include<bits/stdc++.h>
using namespace std;
int vis[20][20];
char a[20][20];
int n, m;
int step_x[4] = {-1, 1, 0, 0}, step_y[4] = {0, 0, -1, 1};
struct data {
int x;
int y;
};
data s, p;
queue<data> q;
int BFS() {
while (!q.empty()) {
p = q.front();
vis[p.x][p.y] = 1; // 标记当前位置
q.pop();
if (a[p.x][p.y] == 'T') // 找到出口
return 1;
else {
for (int i = 0; i < 4; i++) {
int h = p.x + step_x[i];
int l = p.y + step_y[i];
if (a[h][l] != '*' && !vis[h][l] && h >= 0 && h < n && l >= 0 && l < m) {
data temp;
temp.x = h;
temp.y = l;
q.push(temp);
}
}
}
}
return 0;
}
```
C语言实现走迷宫问题可以使用DFS和BFS两种方法解决,都是使用递归函数或队列来实现搜索算法。
- 1
- 2
前往页