数据结构算法，用C语言完成，
迷宫寻路：以一个的长方阵表示迷宫，用0和1分别表示迷宫中的通路和障碍，将迷宫的长方阵存储在相关数据文件中，迷宫数据从该文件中读取。找到一条从入口到出口的通路，或得到没有通路的结论。将找到的通路以三元组的形式输出，表示经过节点的坐标，表示从入口出发达到该节点的距离，每走一步距离加1。最终输出全部通路，并统计路径距离。
为了实现迷宫寻路，可以使用深度优先搜索或广度优先搜索算法。以下是使用深度优先搜索算法的示例C语言代码：
#include <stdio.h>
#include <stdlib.h>
#define ROW 10 // 迷宫的行数
#define COL 10 // 迷宫的列数
#define MAX_PATH 100 // 最大路径长度
int maze[ROW][COL]; // 存储迷宫数据
int path[MAX_PATH][3]; // 存储路径
int path_count = 0; // 路径数量
int visited[ROW][COL]; // 记录节点是否已经被访问
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向
void read_maze(const char* filename) {
FILE* fp = fopen(filename, "r");
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
fscanf(fp, "%d", &maze[i][j]);
}
}
fclose(fp);
}
int dfs(int row, int col, int step) {
visited[row][col] = 1;
path[step][0] = row;
path[step][1] = col;
path[step][2] = step;
if (row == ROW - 1 && col == COL - 1) {
path_count++;
for (int i = 0; i <= step; i++) {
printf("(%d,%d,%d)", path[i][0], path[i][1], path[i][2]);
if (i < step) {
printf("->");
}
}
printf("\n");
return 1;
}
for (int i = 0; i < 4; i++) {
int r = row + dir[i][0];
int c = col + dir[i][1];
if (r >= 0 && r < ROW && c >= 0 && c < COL && maze[r][c] == 0 && !visited[r][c]) {
if (dfs(r, c, step + 1)) {
return 1;
}
}
}
visited[row][col] = 0;
return 0;
}
int main() {
read_maze("maze.txt");
dfs(0, 0, 0);
printf("Total paths: %d\n", path_count);
return 0;
}
在上面的示例代码中，read_maze函数从文件中读取迷宫数据，dfs函数使用深度优先搜索算法进行迷宫寻路，并输出找到的路径。
maze.txt文件应该包含一个10x10的迷宫矩阵，其中0表示通路，1表示障碍。例如，下面是一个迷宫的示例文件内容：
0 1 1 0 1 0 0 1 1 0
0 0 1 0 0 1 1 0 0 0
0 0 0 0 1 1 1 0 1 1
1 1 0 1 0 0 1 0 0 0
1 0 0 1 1 1 1 0 0 1
0 0 1 0 0 1 1 0 1 1
1 0 1 1 0 0 0 0 0 0
0 0 1 1 1 0 0 1 0 0
1 1 1 0 1 0 1 1 1 0
0 0 1 0 0 1 1 0 1 0
这个迷宫矩阵表示了一个从左上角(0,0)到右下角(9,9)的迷宫，其中0表示通路，1表示障碍。
以下是一个可能的 C 语言实现，其中使用了深度优先搜索算法来寻找迷宫的通路。
#include <stdio.h>
#include <stdlib.h>
#define MAX_ROW 20
#define MAX_COL 20
// 定义一个表示迷宫的二维数组
int maze[MAX_ROW][MAX_COL];
// 定义一个表示走过的路径的二维数组，初始化为0
int visited[MAX_ROW][MAX_COL];
// 定义一个表示当前路径的坐标数组，用于输出路径
int path[MAX_ROW * MAX_COL][3];
// 定义全局变量表示起点和终点
int start_row, start_col, end_row, end_col;
// 定义一个全局变量表示路径的长度
int path_len;
// 定义一个表示四个方向的偏移量数组，用于搜索邻居节点
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};
// 深度优先搜索算法
void dfs(int row, int col, int dist) {
// 如果已经到达终点，输出路径，并返回
if (row == end_row && col == end_col) {
for (int i = 0; i < path_len; i++) {
printf("(%d, %d, %d) ", path[i][0], path[i][1], path[i][2]);
}
printf("(%d, %d, %d)\n", row, col, dist);
return;
}
// 将当前节点加入路径
path[path_len][0] = row;
path[path_len][1] = col;
path[path_len][2] = dist;
path_len++;
visited[row][col] = 1;
// 搜索四个方向的邻居节点
for (int i = 0; i < 4; i++) {
int r = row + dr[i];
int c = col + dc[i];
// 判断邻居节点是否可达
if (r >= 0 && r < MAX_ROW && c >= 0 && c < MAX_COL &&
maze[r][c] == 0 && visited[r][c] == 0) {
dfs(r, c, dist + 1);
}
}
// 将当前节点从路径中删除
path_len--;
visited[row][col] = 0;
}
int main() {
// 从文件中读取迷宫数据
FILE *fp = fopen("maze.txt", "r");
if (fp == NULL) {
printf("Cannot open file.\n");
exit(1);
}
for (int i = 0; i < MAX_ROW; i++) {
for (int j = 0; j < MAX_COL; j++) {
fscanf(fp, "%d", &maze[i][j]);
visited[i][j] = 0;
}
}
fclose(fp);
// 设置起点和终点
start_row = 0;
start_col = 0;
end_row = MAX_ROW - 1;
end_col = MAX_COL - 1;
// 初始化路径长度为0
path_len = 0;
// 开始搜索
dfs(start_row, start_col, 0);
return 0;
最简单的方法是深度优先搜索：首先从起点开始搜索，如果产生了新的可行解，则遍历可选的每一个节点，根据规则将当前节点加到路径之中，然后判断该路径是否满足结束条件，如果满足则存储该路径，或者继续搜索下一个节点。重复此过程，直到找到一条完整出路为止。
C语言实现：
#include < stdio.h >
#define N 4 //可代表 4*4 的迷宫
enum {RIGHT, DOWN, LEFT, UP}; // 方向
struct MazePosition
{
int row;
int col;
int direction;
int distance;
}stack[100];
int top = 0;
//迷宫初始状态
int maze[N][N] =
{{1, 1, 0, 1},
{0, 0, 1, 0},
{1, 0, 1, 0},
{0, 1, 0, 1}};
int reached[N][N] = {0}; //标记是否到达
// 判断该位置是否是安全的
bool canStep(int i, int j)
{
if(i < 0 || i >= N || j < 0 || j >= N || maze[i][j] == 1 || reached[i][j] == 1)
return false;
return true;
}
// 走一步
void step(int i, int j, int direction)
{
maze[i][j] = 2;
reached[i][j] = 1;
top++;
stack[top].row = i;
stack[top].col = j;
stack[top].direction = direction;
stack[top].distance = stack[top-1].distance + 1;
}
//后退一步
void backtrack()
{
maze[stack[top].row][stack[top].col] = 0;
top--;
}
// 寻找出路
bool findRoute()
{
// 标记 入口
step(3, 0, RIGHT);
// 如果最顶端位置不是出口
while(stack[top].row != 0 || stack[top].col != 3)
{
//当前位置
int currentRow = stack[top].row;
int currentCol = stack[top].col;
// 尝试分别向上下左右四个方向移动
// 如果可以移动，则移动，否则后退
if(canStep(currentRow, currentCol+1))
step(currentRow, currentCol+1, RIGHT);
else if(canStep(currentRow+1, currentCol))
step(currentRow+1, currentCol, DOWN);
else if(canStep(currentRow, currentCol-1))
step(currentRow, currentCol-1, LEFT);
else if(canStep(currentRow-1, currentCol))
step(currentRow-1, currentCol, UP);
else
backtrack();
}
// 找到出路，输出路径
if(stack[top].row == 0 && stack[top].col == 3)
{
printf("找到出路，各步坐标如下：\n");
for(int i = 0; i <= top; i++)
{
printf("(%d, %d): %d\n", stack[i].row, stack[i].col, stack[i].direction);
}
printf("路径总长度: %d \n", stack[top].distance);
return true;
}
else
return false;
}
int main()
{
findRoute();
return 0;
}
希望对您有用，应该写的很详细了，如果有帮到可以点个采纳哦，写程序不易
该回答引用ChatGPT
#include <stdio.h>
#include <stdlib.h>
#define ROWS 10
#define COLS 10
/* 迷宫地图 */
int maze[ROWS][COLS] = {
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
{1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
{1, 0, 0, 0, 0, 1, 1, 0, 0, 1},
{1, 0, 1, 1, 1, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 1, 0, 0, 0, 0, 1},
{1, 0, 1, 0, 0, 0, 1, 0, 0, 1},
{1, 0, 1, 1, 1, 0, 1, 1, 0, 1},
{1, 1, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
};
/* 记录迷宫节点的状态 */
enum NodeState {
UNVISITED, /* 未访问 */
VISITED, /* 已访问 */
WALL /* 墙 */
};
/* 迷宫节点 */
struct Node {
int x, y; /* 节点坐标 */
int dist; /* 到起点的距离 */
enum NodeState state; /* 节点状态 */
};
/* 栈结构 */
struct Stack {
int top; /* 栈顶指针 */
struct Node* data[ROWS * COLS]; /* 存储节点指针的数组 */
};
/* 初始化栈 */
void initStack(struct Stack* s) {
s->top = -1;
}
/* 压栈 */
void push(struct Stack* s, struct Node* node) {
s->data[++s->top] = node;
}
/* 弹栈 */
struct Node* pop(struct Stack* s) {
if (s->top == -1) {
return NULL;
}
return s->data[s->top--];
}
/* 判断栈是否为空 */
int isEmpty(struct Stack* s) {
return s->top == -1;
}
/* 获取栈顶元素 */
struct Node* top(struct Stack* s) {
if (s->top == -1) {
return NULL;
}
return s->data[s->top];
}
/* 判断节点是否可访问 */
int isNodeAccessible(int x, int y) {
if (x < 0 || x >= ROWS || y < 0 || y >= COLS) {
return 0;
}
return maze[x][y] == 0;
}
/* 判断节点是否
https://blog.csdn.net/qq_55918164/article/details/125737437
迷宫寻路是一种用于寻找迷宫中的通路的问题，它可以通过一些特定的数据结构和算法来实现，例如栈和回溯法
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100 //定义栈的最大容量
#define ROW 5 //定义迷宫的行数
#define COL 5 //定义迷宫的列数
//定义一个结构体，表示栈中的元素，包括坐标和距离
typedef struct {
int x; //横坐标
int y; //纵坐标
int dist; //距离
} SElemType;
//定义一个结构体，表示栈，包括栈顶指针和栈中的元素
typedef struct {
SElemType data[MAXSIZE]; //栈中的元素
int top; //栈顶指针
} SqStack;
//定义一个函数，初始化栈，将栈顶指针置为-1
void InitStack(SqStack *S) {
S->top = -1;
}
//定义一个函数，判断栈是否为空，如果为空，返回1，否则返回0
int StackEmpty(SqStack S) {
if (S.top == -1) {
return 1;
} else {
return 0;
}
}
//定义一个函数，判断栈是否为满，如果为满，返回1，否则返回0
int StackFull(SqStack S) {
if (S.top == MAXSIZE - 1) {
return 1;
} else {
return 0;
}
}
//定义一个函数，入栈，将元素e压入栈中，如果成功，返回1，否则返回0
int Push(SqStack *S, SElemType e) {
if (StackFull(*S)) {
return 0;
} else {
S->top++;
S->data[S->top] = e;
return 1;
}
}
//定义一个函数，出栈，将栈顶元素弹出，并赋值给e，如果成功，返回1，否则返回0
int Pop(SqStack *S, SElemType *e) {
if (StackEmpty(*S)) {
return 0;
} else {
*e = S->data[S->top];
S->top--;
return 1;
}
}
//定义一个函数，获取栈顶元素，不弹出，并赋值给e，如果成功，返回1，否则返回0
int GetTop(SqStack S, SElemType *e) {
if (StackEmpty(S)) {
return 0;
} else {
*e = S.data[S.top];
return 1;
}
}
//定义一个函数，打印栈中的元素，从栈顶到栈底
void PrintStack(SqStack S) {
int i;
for (i = S.top; i >= 0; i--) {
printf("(%d,%d,%d) ", S.data[i].x, S.data[i].y, S.data[i].dist);
}
printf("\n");
}
//定义一个函数，读取迷宫数据，将迷宫存储在二维数组中，返回迷宫的入口和出口
void ReadMaze(int maze[ROW][COL], SElemType *start, SElemType *end) {
FILE *fp; //定义一个文件指针
int i, j; //定义两个循环变量
fp = fopen("maze.txt", "r"); //打开迷宫数据文件，以只读模式
if (fp == NULL) { //判断文件是否打开成功，如果失败，打印错误信息并退出程序
printf("File open error!\n");
exit(1);
}
for (i = 0; i < ROW; i++) { //循环读取迷宫数据，存储在二维数组中
for (j = 0; j < COL; j++) {
fscanf(fp, "%d", &maze[i][j]); //从文件中读取一个整数，赋值给二维数组的元素
if (maze[i][j] == 2) { //判断是否是入口，如果是，记录入口的坐标和距离
start->x = i;
start->y = j;
start->dist = 0;
}
if (maze[i][j] == 3) { //判断是否是出口，如果是，记录出口的坐标和距离
end->x = i;
end->y = j;
end->dist = 0;
}
}
}
fclose(fp); //关闭文件
}
//定义一个函数，打印迷宫数据，将迷宫以二维数组的形式输出
void PrintMaze(int maze[ROW][COL]) {
int i, j; //定义两个循环变量
for (i = 0; i < ROW; i++) { //循环打印迷宫数据，每行一个换行符
for (j = 0; j < COL; j++) {
printf("%d ", maze[i][j]); //打印二维数组的元素，每个元素之间一个空格符
}
printf("\n");
}
}
//定义一个函数，判断当前位置是否可以走，如果可以，返回1，否则返回0
int Pass(int maze[ROW][COL], SElemType cur) {
if (cur.x >= 0 && cur.x < ROW && cur.y >= 0 && cur.y < COL && maze[cur.x][cur.y] == 0) {
//判断当前位置是否在迷宫范围内，以及是否是通路，如果是，返回1
return 1;
} else {
//否则，返回0
return 0;
}
}
//定义一个函数，标记当前位置已经走过，将迷宫中的对应位置置为-1
void FootPrint(int maze[ROW][COL], SElemType cur) {
maze[cur.x][cur.y] = -1;
}
//定义一个函数，寻找下一个可以走的位置，将其坐标和距离赋值给next，如果成功，返回1，否则返回0
int NextPos(int maze[ROW][COL], SElemType cur, SElemType *next, int di) {
//定义一个二维数组，表示四个方向的偏移量，分别是上，右，下，左
int offset[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
//根据当前位置和方向，计算下一个位置的坐标
next->x = cur.x + offset[di][0];
next->y = cur.y + offset[di][1];
//判断下一个位置是否可以走，如果可以，将距离加1，返回1
if (Pass(maze, *next)) {
next->dist = cur.dist + 1;
return 1;
} else {
//否则，返回0
return 0;
}
}
//定义一个函数，寻找迷宫的通路，如果找到，打印通路，否则打印没有通路
void MazePath(int maze[ROW][COL], SElemType start, SElemType end) {
SqStack S; //定义一个栈，用于存储通路的节点
SElemType cur, next; //定义两个变量，表示当前位置和下一个位置
int di, find; //定义两个变量，表示方向和是否找到通路的标志
InitStack(&S); //初始化栈
cur = start; //将当前位置设为入口
FootPrint(maze, cur); //标记当前位置已经走过
Push(&S, cur); //将当前位置压入栈中
while (!StackEmpty(S)) { //当栈不为空时，循环
GetTop(S, &cur); //获取栈顶元素，赋值给当前位置
if (cur.x == end.x && cur.y == end.y) { //判断当前位置是否是出口，如果是，打印通路，并退出循环
printf("Find a path:\n");
PrintStack(S);
break;
}
di = 0; //将方向设为0，表示从上开始
find = 0; //将是否找到通路的标志设为0，表示没有找到
while (di < 4 && find == 0) { //当方向小于4，且没有找到通路时，循环
if (NextPos(maze, cur, &next, di)) { //判断下一个位置是否可以走，如果可以，标记下一个位置已经走过，将下一个位置压入栈中，将是否找到通路的标志设为1
FootPrint(maze, next);
Push(&S, next);
find = 1;
} else {
//否则，将方向加1，继续寻找下一个位置
di++;
}
}
if (find == 0) { //如果没有找到通路，说明当前位置是死路，将其从栈中弹出，回溯到上一个位置
Pop(&S, &cur);
}
}
if (StackEmpty(S)) { //如果栈为空，说明没有找到通路，打印没有通路
printf("No path.\n");
}
}
以下是一种可能的迷宫寻路算法的实现，该算法基于深度优先搜索，并使用了栈来跟踪搜索路径。
首先，需要定义一个结构体来表示坐标点和距离：
typedef struct {
int x;
int y;
int dist;
} point;
然后，读取迷宫数据文件并将其存储在一个二维数组中：
int maze[MAX_ROWS][MAX_COLS];
FILE *fp = fopen("maze.txt", "r");
for (int i = 0; i < MAX_ROWS; i++) {
for (int j = 0; j < MAX_COLS; j++) {
fscanf(fp, "%d", &maze[i][j]);
}
}
fclose(fp);
接下来，定义一个栈来跟踪搜索路径，并初始化它：
point stack[MAX_ROWS * MAX_COLS];
int top = -1;
void push(point p) {
stack[++top] = p;
}
point pop() {
return stack[top--];
}
void clear() {
top = -1;
}
然后，定义一个函数来检查给定的坐标是否是迷宫中的合法位置：
bool is_valid(int x, int y) {
return (x >= 0 && x < MAX_ROWS && y >= 0 && y < MAX_COLS && maze[x][y] == 0);
}
接下来，定义一个深度优先搜索函数来查找通路：
void dfs(int x, int y) {
if (!is_valid(x, y)) {
return;
}
push((point) { x, y, top == -1 ? 0 : stack[top].dist + 1 });
if (x == MAX_ROWS - 1 && y == MAX_COLS - 1) {
// 找到了通路
printf("找到了一条通路：");
for (int i = 0; i <= top; i++) {
printf("(%d,%d,%d) ", stack[i].x, stack[i].y, stack[i].dist);
}
printf("\n");
return;
}
maze[x][y] = 1;
dfs(x - 1, y); // 上
dfs(x, y + 1); // 右
dfs(x + 1, y); // 下
dfs(x, y - 1); // 左
maze[x][y] = 0;
pop();
}
最后，调用该函数以查找通路并输出结果：
int main() {
dfs(0, 0);
return 0;
}
这个实现只会输出一条通路，如果想要输出所有的通路，可以在找到一条通路后继续搜索，直到找到所有的通路为止。同时，还可以在输出通路时统计路径距离并记录所有的通路。
迷宫寻路算法的实现，使用了广度优先搜索算法。
首先，我们需要定义迷宫的长方阵，并读取迷宫数据文件，将其存储在一个二维数组中。假设迷宫的入口为(0, 0)，出口为(n-1, m-1)，其中n和m为迷宫的长和宽。
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100
#define MAX_M 100
int maze[MAX_N][MAX_M]; // 迷宫的长方阵
int dist[MAX_N][MAX_M]; // 从入口到每个节点的距离
int n, m; // 迷宫的长和宽
// 读取迷宫数据文件
void read_maze(const char *filename) {
FILE *fp;
fp = fopen(filename, "r");
if (fp == NULL) {
fprintf(stderr, "Cannot open file %s\n", filename);
exit(1);
}
// 读取迷宫的长和宽
fscanf(fp, "%d %d", &n, &m);
// 读取迷宫的数据
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
fscanf(fp, "%d", &maze[i][j]);
}
}
fclose(fp);
}
接下来，我们定义一个队列来存储待访问的节点，使用BFS算法从入口开始搜索。搜索过程中，我们用dist数组记录从入口到每个节点的距离，用pre数组记录每个节点的前一个节点。
typedef struct {
int x, y; // 节点的坐标
int d; // 节点的距离
} Node;
// 队列的定义
Node q[MAX_N * MAX_M];
int head, tail;
// BFS算法寻找迷宫的通路
void bfs(int sx, int sy, int gx, int gy) {
// 初始化队列
head = tail = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
dist[i][j] = -1; // 初始距离为-1，表示未访问过
}
}
// 将起点加入队列
Node s = {sx, sy, 0};
dist[sx][sy] = 0;
q[tail++] = s;
// 循环遍历队列中的节点，直到找到终点或队列为空
while (head < tail) {
Node u = q[head++];
if (u.x == gx && u.y == gy) {
// 找到了终点，输出路径
printf("(%d, %d, %d)", gx, gy, u.d);
int x = gx, y = gy;
while (x != sx || y != sy) {
Node v = q[dist[x][y]-1];
printf(" -> (%d, %