用栈解决迷宫问题

一、

因为栈是后进先出的特性，所以说一般用栈都是通过dfs来解决迷宫问题。如果用队列的话就是通过bfs来解决。

二、

c++代码：

#include<iostream>
#include<cstdio>
#include<stdio.h>
#include<string.h>
#include<windows.h>
using namespace std;
const int maxn=1005;
#define MaxSize    100005     //栈最多元素个数
int M=4,N=4;
int w[6][6]=
{
    {1,1,1,1,1,1}
    ,{1,0,0,0,1,1}
    ,{1,0,1,0,0,1}
    ,{1,0,0,0,1,1}
    ,{1,1,0,0,0,1}
    ,{1,1,1,1,1,1}
};
int mg[maxn][maxn];
char s[maxn][maxn];
struct migong
{
    int i;      //路径横坐标
    int j;      //路径纵坐标
    int di;     //方向
} Stack[MaxSize],Path[MaxSize];     //定义栈和存放最短路径的数组
int top=-1;     //栈顶指针
int counts=1;    //路径数计数
int minlen=MaxSize;     //最短路径长度
void mgpath()       //路径为:(1,1)->(M,N)
{
    int i,j,di,finds,k;
    top++;
    Stack[top].i=1;
    Stack[top].j=1;
    Stack[top].di=-1;
    mg[1][1]=-1;        //初始结点进栈
    while(top>-1)       //栈不空时循环
    {
        i=Stack[top].i;
        j=Stack[top].j;
        di=Stack[top].di;
        if(i==M && j==N)        //找到了出口，输出路径
        {
//            cout<<counts<<": ";
//            counts++;
//            for(k=0; k<=top; k++)
//            {
//                cout<<"("<<Stack[k].i<<","<<Stack[k].j<<")"<<" ";
//
//            }
//            cout<<endl;
            if(top+1<minlen)        //比较输出最短路径
            {
                for(k=0; k<=top; k++)
                    Path[k]=Stack[k];
                minlen=top+1;
            }
            mg[Stack[top].i][Stack[top].j]=0;   //让该位置变为其他路径的可走结点
            top--;
            i=Stack[top].i;
            j=Stack[top].j;
            di=Stack[top].di;
        }
        finds=0;
        while(di<4 && finds==0)      //找下一个可走结点
        {
            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(mg[i][j]==0)   //因为地图外边围了一层墙，所以不需要判断边界
                finds=1;
        }
        if(finds == 1)       //找到了下一个可走结点
        {
            Stack[top].di=di;   //修改原栈顶元素的di值
            top++;      //下一个可走结点进栈
            Stack[top].i=i;
            Stack[top].j=j;
            Stack[top].di=-1;
            mg[i][j]=-1;        //避免重复走到该结点
        }
        else
        {
            mg[Stack[top].i][Stack[top].j]=0;   //让该位置变为其他路径的可走结点
            top--;
        }
    }
    cout<<"最短路径如下(输出结果以坐标显示)"<<endl;
    cout<<"长度:  "<<minlen<<endl;
    cout<<"路径:  "<<endl;
    for(k=0; k<minlen; k++)
    {
        cout<<"("<<Path[k].i<<","<<Path[k].j<<")"<<" ";
    }
}
int main()
{
    int x;
    while(1)
    {
        system("cls");
        printf ( "             迷宫系统                                            
");
        printf ( "                                                                 
");
        printf ( "                                                                 
");
        printf ("--------------------------------------                           
");
        printf ("--------------------------------------
");
        printf ("--------丨[0]重构地图            丨---
");
        printf ("--------丨[1]使用默认地图        丨---
");
        printf ("--------丨[2]结束                丨---
");
        printf ("----------输入相应数字----------------
");
        printf ("---------------------------------------                           
");
        printf ( "                                                                 
");
        printf ( "                                                                 
");
        scanf("%d",&x);
        if(x==0)
        {
            system("cls");
            printf("            重构地图
");
            printf("输入内容请以空格或者换行分隔开，且0代表此处可走，1代表此处不可行
");
            printf("
现在请输入地图是几行几列
");
            int n,m;
            memset(mg,0,sizeof(mg));
            scanf("%d%d",&n,&m);
            int flag=0;
            printf("
请输入地图,请保证左上角和右下角都为0
");
            for(int i=1; i<=n; ++i)
            {

                scanf("%s",s[i]+1);
                mg[i][0]=mg[i][m+1]=1;
            }
            for(int j=1; j<=m; ++j)
            {
                mg[0][j]=mg[n+1][j]=1;
            }
            for(int i=1;i<=n;++i)
            {
                for(int j=1;j<=m;++j)
                {
                    mg[i][j]=s[i][j]-'0';
                }
            }
            M=n;
            N=m;

            //cout<<"迷宫所有路径如下:"<<endl;
            mgpath();
            system("pause");
        }
        else if(x==1)
        {
            system("cls");
            M=N=4;
            for(int i=0; i<6; ++i)
            {
                for(int j=0; j<6; ++j)
                {
                    mg[i][j]=w[i][j];
                }
            }
            mgpath();
            system("pause");
        }
        else break;
    }
    return 0;
}