求解迷宫所有可能的通路
1）问题描述
以一个M*N的长方阵表示迷宫，0和1分别表示迷宫中的通路和墙壁。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出米有通路的结论。
2）基本要求
a.实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一个坐标的方向。
b.编写递归形式的算法，求得迷宫中所有可能的通路。
3）测试数据
迷宫的测试数据如下：左上角（1,1）为入口，右下角（8,9）为出口。
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0
4）实现提示
计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则，沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则设定的迷宫没有通路。
可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（m，n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。
https://blog.csdn.net/qq_35960743/article/details/126581640
一样的题目吧
#include<stdio.h>
#include<time.h>
#include<math.h>
#include <stdlib.h>
///墙和路径的标识
#define wall 0
#define route 1
#define path 3
#define MaxSize 100///规定栈空间最大是100
struct MG{
int i;
int j;
int di; ///记录方向
}Stack[MaxSize];///栈:存放路径
int top=-1;
///声明函数
void CreateMaze(int **maze, int x, int y);
void mgpath(int **maze,int M, int N);
int main() {
srand((unsigned)time(NULL));/***生成随机数***/
int M,N;
printf("请输入迷宫长度M,宽度N(长宽差2，空格间隔)\n");
scanf("%d %d/n",&M,&N);
M=M+2;N=N+2;///加上外侧包围墙体，最外侧包围路径。
int i,j;
int **Maze = (int**)malloc(M * sizeof(int *));
for(i=0;i<M;i++){
Maze[i]=(int*)malloc(N * sizeof(int));
}/***int *a=(int*)malloc(n*sizeof(int));
表示定义一个int类型的指针变量a，
并申请n*sizeof(int)个字节（即4*n个字节）的存储空间。***/
///防止搜索路时超出边界，把最外围层设为路径。
for (i=0; i<M; i++){
Maze[i][0]=route;
Maze[i][N-1]=route;
}
for (i=0; i<N; i++){
Maze[M-1][i]=route;
Maze[0][i]=route;
}
///创造迷宫，（2，2）为起点
CreateMaze(Maze, 2, 2);
///画迷宫的入口
Maze[2][1] = route;
///算法随机性，出口不一定在（M-3,N-2）处，需要寻找出口。
for (i=M-3; i>=0; i--) {
if (Maze[i][M-3]==route) {
Maze[i][N-2] = route;
break;
}
}
///打印迷宫。
for (i=0; i<M; i++) {
for (j=0; j<N; j++) {
if (Maze[i][j]==route) {
printf(" 0 ");
}
else {
printf(" 1 "); ///█墙壁，测试用。
}
}
printf("\n");
}
printf("迷宫路径如下：\n");
mgpath(Maze,M,N);
for(i=0;i<M;i++)
free((int *)Maze[i]);
free((int *)Maze);
return 0;
}
void CreateMaze(int **maze, int x, int y) {
maze[x][y] = route;
///确保四个方向随机
int direction[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };///向上,下,左,右移动
int i,j,k;
for (i=0; i<4; i++) {
int r = rand() % 4;
int t = direction[0][0];
direction[0][0] = direction[r][0];
direction[r][0] = t;
t = direction[0][1];
direction[0][1] = direction[r][1];
direction[r][1] = t;
}
///决定下一步去往那个方向
for (i=0; i<4; i++) {
int dx=x;
int dy=y;
int range = 1;
while (range>0) {
dx += direction[i][0];
dy += direction[i][1];
///排除掉回头路
if (maze[dx][dy] == route) {
break;
}
///判断是否挖穿路径
int count = 0;
for (j=dx-1;j<dx+2;j++) {
for (k=dy-1;k<dy+2;k++) {
///abs(j-dx) + abs(k-dy) == 1 确保只判断九宫格的四个特定位置
///abs 绝对值函数
if (abs(j-dx)+abs(k-dy)==1 && maze[j][k]==route){
count++;
}
}
}
if (count > 1) {
break;
}
///确保不会挖穿时，前进
--range;
maze[dx][dy] = route;
}
///没有挖穿危险，以此为节点递归
if (range <= 0) {
CreateMaze(maze, dx, dy);
}
}
}
void mgpath(int **Maze,int M, int N){
int i,j,di;/// i,j表示当前位置，di为方向
int find,k;/// find为是否找到了可走点，找到为1，k用于读取
top++;
Stack[top].i=2; ///初始位置(2,2)
Stack[top].j=1;
Stack[top].di=-1;
Maze[2][1]= path;
while(top>-1){ ///只要栈Stack不为空就继续走
i=Stack[top].i;
j=Stack[top].j;
di=Stack[top].di;
if(i==M-3&&j==N-2) ///找到了出口，输出路径
{
for(k=0; k<=top; k++)
{
printf("(%d,%d) ",Stack[k].i,Stack[k].j);
}
break;
}
find=0;
///di:0上1右2下3左四个方向，找可走点
while(di<4 && find==0){ ///在4个方向内，寻找可走点
di++;
switch(di)
{
case 0:i=Stack[top].i-1;
j=Stack[top].j;
break; ///上面
case 1:i=Stack[top].i;
j=Stack[top].j+1;
break; ///右边
case 2:i=Stack[top].i+1;
j=Stack[top].j;
break; ///下面
case 3:i=Stack[top].i;
j=Stack[top].j-1;
break; ///左边
}
if(Maze[i][j]==route){///找到可走点
find=1;
}
}
if(find == 1) ///找到了下一个可走结点
{
Stack[top].di=di; ///修改原栈顶元素的di值
top++; ///下一个可走结点进栈
Stack[top].i=i;
Stack[top].j=j;
Stack[top].di=-1;
Maze[i][j]=path; ///避免重复走到该结点
}else ///没找到
{
Maze[Stack[top].i][Stack[top].j]=route; ///让该位置变为其他路径的可走结点
top--;
}
}
if(top==-1){
printf("No path!");
}
}
提供参考实例【数据结构课程设计——迷宫问题课程设计报告】，链接：https://blog.csdn.net/aspireone/article/details/7712449?spm=1001.2101.3001.6650.3&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-3-7712449-blog-126581640.pc_relevant_multi_platform_whitelistv4&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-3-7712449-blog-126581640.pc_relevant_multi_platform_whitelistv4&utm_relevant_index=6
【推荐理由：讲解细致，讲述了数据结构、基本算法、以及运行调试与结果，代码可执行】