给一个C语言版本的答案
时间: 2024-03-18 10:41:20 浏览: 22
好的,这是一个基于深度优先搜索的C语言代码实现,希望能帮到您。
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 55
// 迷宫的大小
int n, m;
// 迷宫的矩阵
int maze[MAXN][MAXN];
// 标记矩阵,记录哪些位置已经走过
int mark[MAXN][MAXN];
// 方向数组,表示上下左右四个方向
int go[][2] = {
1, 0,
-1, 0,
0, 1,
0, -1
};
// 搜索函数,x、y表示当前位置的坐标,step表示当前的步数
int dfs(int x, int y, int step) {
int i;
// 如果当前位置是终点,返回当前步数
if (x == n && y == m) {
return step;
}
// 遍历四个方向
for (i = 0; i < 4; i++) {
int nx = x + go[i][0], ny = y + go[i][1];
// 判断是否越界
if (nx < 1 || nx > n || ny < 1 || ny > m) {
continue;
}
// 判断是否可以走
if (maze[nx][ny] == 0 && mark[nx][ny] == 0) {
mark[nx][ny] = 1; // 标记为已经走过
int res = dfs(nx, ny, step + 1);
if (res > 0) {
return res;
}
mark[nx][ny] = 0; // 恢复为未走过,以便搜索其他方向
}
}
// 如果四个方向都不能到达终点,返回-1
return -1;
}
int main() {
int i, j;
scanf("%d%d", &n, &m);
// 读入迷宫矩阵
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
scanf("%d", &maze[i][j]);
}
}
// 初始化标记矩阵
memset(mark, 0, sizeof(mark));
// 从起点开始搜索
mark[1][1] = 1;
printf("%d\n", dfs(1, 1, 0));
return 0;
}
```
这段代码基于深度优先搜索思想,从起点开始搜索,每次遍历四个方向,如果某个方向可以到达并且没有走过,就标记为已经走过,并继续从这个方向开始搜索,直到到达终点或者所有的方向都不能到达终点。如果能到达终点,返回当前步数,否则返回-1。