问题：

以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

基本要求

输入的形式和范围：

非递归：行列为整型，坐标为整型

递归：迷宫以整型二维数组形式输入

输出的形式：非递归输出三元组通路和方阵通路；

递归以方阵输出迷宫和所有通路；

1、非递归算法，求一条通路输出三元组形式如：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），…和方阵通路；

2、递归算法，求得迷宫中所有可能的通路，以方阵形式输出迷宫及其通路。

递归解法：

#include <stdio.h>
#include <malloc.h>
#define M 6
#define N 6
#define END N-2
int flag=0;
typedef struct
{
    int x,y,d;
}position;

/*创建迷宫*/
void creat_maze(int a[][M])
{
    int i,j;
    for(i=0;i<=N-1;i++)
        for(j=0;j<=M-1;j++)
        scanf("%1d",&a[i][j]);
}

position nextq(int maze[][M],position q)
{
    if(q.d==0)
        q.y++;
    else if(q.d==1)
        q.x++;
    else if(q.d==2)
        q.y--;
    else if(q.d==3)
        q.x--;
    return q;
}
void initialmat(int route[][M])       //初始化输出路径图
{
    int i,j;
    for(i=0;i<N;i++)
        for(j=0;j<M;j++)
            route[i][j]=1;
}
void print_maze(int mat[][M])        //输出迷宫
{
    int i,j;
    for(i=0;i<N;i++)
        {
        for(j=0;j<M;j++)
           printf("%d ",mat[i][j]);
           printf("\n");
        }

}
void MazePath(int maze[][M],int route[][M],position ps)
{
    position q;
    route[ps.x][ps.y]=0;
    maze[ps.x][ps.y]=-1;
    q=nextq(maze,ps);
    q.d=0;
    if(q.x==END&&q.y==END)
    {
        flag++;
        printf("\n第%d条路:\n",flag);
        route[END][END]=0;
        print_maze(route);
        route[END][END]=1;
    }
    else if(maze[q.x][q.y]==0)
        MazePath(maze,route,q);
    if(ps.d<=3)
    {
        ps.d++;
        MazePath(maze,route,ps);
    }
    route[ps.x][ps.y]=1;
    maze[ps.x][ps.y]=0;
}
void main()
{
    int maze[N][M],route[N][M];
    position ps;
    ps.x=ps.y=1;
    ps.d=0;
    printf("输入一个迷宫(%d*%d):\n",N,M);
    creat_maze(maze);
    printf("\n输出该迷宫:\n");
    print_maze(maze);
    printf("输出从(1,1)到(%d,%d)的所有通路:\n",N-2,M-2);
    initialmat(route);
    MazePath(maze,route,ps);
}

非递归解法：

#include<stdio.h>
#include<stdlib.h>
#define Elemtype int
#define MAXSIZE 50
typedef struct
{
    int x,y;
}mark;               //起点、终点坐标

typedef struct
{
    Elemtype x,y;    //迷宫数组坐标(x,y)
    int d;    //下一步的方向
}TriMatrix;

typedef struct LStackNode
{
    TriMatrix elem;
    struct LStackNode *next;
}LStack,*PLStack;

//栈的基本操作

PLStack InitStack(PLStack S)
{
    S=NULL;
	return S;
}

int StackEmpty(PLStack S)
{
    if(S==NULL)  return 1;
    else return 0;
}

PLStack Push(PLStack S,TriMatrix e)   //入栈
{
    PLStack P;
    P=(PLStack)malloc(sizeof(LStack));
    P->elem=e;
    P->next=S;
    S=P;
	return S;
}

PLStack Delete(PLStack S)   //删除栈头
{
    PLStack P;
    P=S;
	if(!StackEmpty(S))
	{
        S=S->next;
        free(P);
        return S;
	}
}

TriMatrix Pop(PLStack S,TriMatrix e)  //出栈
{
    if(!StackEmpty(S))
	{
        e=S->elem;
        return e;
	}
}

void MazePath(mark start,mark end,
              Elemtype maze[MAXSIZE][MAXSIZE],
              int m,int n,int diradd[4][2])   //寻找路径
{
    int i,j,d;
    int a,b;
    TriMatrix elem,e;
    PLStack S1,S2;
    S1=InitStack(S1);
    S2=InitStack(S2);
    maze[start.x][start.y]=2;   //修改入口坐标，做标记
    elem.x=start.x;
    elem.y=start.y;
    elem.d=0;  //开始为0
    S1=Push(S1,elem);
    while(!StackEmpty(S1))  //栈不空，有路可走
    {
        elem=Pop(S1,elem);
		S1=Delete(S1);
        i=elem.x;
        j=elem.y;
        d=elem.d+1;
        while(d<=4)
        {
            a=i+diradd[d-1][0];
            b=j+diradd[d-1][1];
            if(a==end.x&&b==end.y&&maze[a][b]==0)  //出口
            {
                elem.x=i;
                elem.y=j;
                elem.d=d;
                S1=Push(S1,elem);
                elem.x=a;
                elem.y=b;
                elem.d=0;   //方向输出为0，判断是否为出口
                S1=Push(S1,elem);
                printf("\n1=东 2=南 3=西 4=北 0为走出迷宫\n\n路径为:(行坐标，列坐标，方向)\n");
                while(S1)  //逆置序列 并输出路径
                {
                    e=Pop(S1,e);
					S1=Delete(S1);
                    S2=Push(S2,e);
                }
                while(S2)
                {
                    e=Pop(S2,e);
					S2=Delete(S2);
                    printf("-->(%d,%d,%d)",e.x,e.y,e.d);maze[e.x][e.y]=3;
                }
				printf("\n\n");
				for(i=0;i<=m+1;i++){
                for(j=0;j<=n+1;j++)
                    if(maze[i][j]==3) printf("0 ");
                    else printf("1 ");
                    printf("\n");
                }
                return;
            }//if
            if(maze[a][b]==0)
            {
                maze[a][b]=2;
                elem.x=i;
                elem.y=j;
                elem.d=d;
                S1=Push(S1,elem);
                i=a;  j=b;  d=0;
            }
            d++;
        }
    }
    printf("没有出迷宫的路径\n");
}

//建立迷宫
void initmaze(int maze[MAXSIZE][MAXSIZE],int m,int n)
{
    int i,j;
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
        maze[i][j]=rand()%2;
    for(i=0;i<=m+1;i++)
    {
        maze[i][0]=maze[i][n+1]=1;
    }
    for(j=0;j<=n+1;j++)
    {
        maze[0][j]=maze[m+1][j]=1;
    }
    printf("输出迷宫:\n");
    for(i=0;i<=m+1;i++)
    {
        for(j=0;j<=n+1;j++)
        printf("%d ",maze[i][j]);
        printf("\n");
    }
}

void main()
{
    int maze[MAXSIZE][MAXSIZE];
    mark start,end;
    int m,n;  //迷宫行列
    printf("输入迷宫的行数m和列数n:\n");
    scanf("%d%d",&m,&n);
    int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
    initmaze(maze,m,n);
    printf("输入入口坐标和出口坐标:\n");
    scanf("%d%d%d%d",&start.x,&start.y,&end.x,&end.y);
    MazePath(start,end,maze,m,n,add);
}

写在最后：对于准备学习C/C++编程的小伙伴，如果你想更好的提升你的编程核心能力（内功）不妨从现在开始！

编程学习书籍分享：

编程学习视频分享：

整理分享（多年学习的源码、项目实战视频、项目笔记，基础入门教程）

欢迎转行和学习编程的伙伴，利用更多的资料学习成长比自己琢磨更快哦！

对于C/C++感兴趣可以关注小编在后台私信我：【编程交流】一起来学习哦！可以领取一些C/C++的项目学习视频资料哦！已经设置好了关键词自动回复，自动领取就好了！