C语言代码实现给定一个m*n大小的矩阵,其中的每个元素,如果为1则表示该位置为墙,为0则表示该位置为空。 坐标(1,1)为起点S,坐标(m,n)的位置为终点T(默认这两个位置的元素为0)。请设计一个程序,判定该迷宫是否存在一条“简单”路径连接S和T(即该路径上的点对应的所有元素皆为0):如果存在则返回该路径;否则返回“无”。 注意在走该迷宫时,每次只能选择“上下左右”四个方向中的一个进行移动。如果将要移动的位置有墙,则待在原地。
时间: 2023-06-19 14:08:19 浏览: 129
螺旋阵,请设计算法完成螺旋阵的输出,具有要求为:输入一个m行n列的矩阵,按顺时针螺旋顺序输出矩阵中的所有元素
以下是使用深度优先搜索(DFS)算法实现的C语言代码:
```c
#include <stdio.h>
#define MAX_M 100
#define MAX_N 100
int maze[MAX_M][MAX_N]; // 迷宫矩阵
int visited[MAX_M][MAX_N]; // 标记矩阵,记录每个位置是否被访问过
int path[MAX_M * MAX_N][2]; // 记录路径,每个位置用一个二元组表示,即行列坐标
int m, n; // 矩阵大小
int found = 0; // 是否找到路径
// 深度优先搜索
void dfs(int x, int y, int step) {
if (x == m && y == n) { // 到达终点
found = 1; // 找到路径
for (int i = 1; i <= step; i++) {
printf("(%d,%d)", path[i][0], path[i][1]);
if (i < step) {
printf(" -> ");
}
}
printf("\n");
return;
}
visited[x][y] = 1; // 标记当前位置为已访问
path[step][0] = x;
path[step][1] = y;
// 向上走
if (x > 1 && maze[x-1][y] == 0 && visited[x-1][y] == 0) {
dfs(x-1, y, step+1);
}
// 向下走
if (x < m && maze[x+1][y] == 0 && visited[x+1][y] == 0) {
dfs(x+1, y, step+1);
}
// 向左走
if (y > 1 && maze[x][y-1] == 0 && visited[x][y-1] == 0) {
dfs(x, y-1, step+1);
}
// 向右走
if (y < n && maze[x][y+1] == 0 && visited[x][y+1] == 0) {
dfs(x, y+1, step+1);
}
visited[x][y] = 0; // 回溯,标记当前位置为未访问
}
int main() {
// 读入迷宫矩阵大小和元素值
scanf("%d %d", &m, &n);
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &maze[i][j]);
}
}
// 从起点开始搜索
dfs(1, 1, 1);
if (!found) { // 没有找到路径
printf("无\n");
}
return 0;
}
```
该代码使用了一个标记矩阵 `visited`,记录每个位置是否被访问过,避免重复访问。同时,使用一个路径记录数组 `path`,每次访问一个新位置时将其加入路径中,如果到达终点则输出该路径。如果没有找到路径,则输出“无”。
阅读全文