[数据结构] 迷宫有关问题（栈和队列，深搜和广搜）

[数据结构] 迷宫问题（栈和队列，深搜和广搜）

代码：

#include <iostream>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

int dx[4]={0,-1,1,0};//方向
int dy[4]={-1,0,0,1};
bool vis[6][6];
int total=0;//多少可到达路径
int sx=1,sy=1;//入口出口坐标
int ex=4,ey=4;
int num[10][10];//广搜时记录到达当前点的最少步数

struct P
{
    int x,y;
}point[40];//用来记录可到达路径

struct PP
{
    int fx,fy;
}path[10][10];//用来记录最短路径坐标增量，用于回溯输出最短路径

char map[6][6]=//地图
{
    {'#','#','#','#','#','#'},
    {'#','.','.','.','#','#'},
    {'#','.','#','.','.','#'},
    {'#','.','.','.','#','#'},
    {'#','#','.','.','.','#'},
    {'#','#','#','#','#','#'}
};

bool ok(int x,int y)//判断当前点是否可走
{
    if(x<0||x>5||y<0||y>5)
        return 0;
    if(map[x][y]=='#')
        return 0;
    if(vis[x][y]==1)
        return 0;
    return 1;
}

void dfs(int x,int y,int step)//深搜可到达路径，参数step对于记录路径来说很重要
{
    if(x==ex&&y==ey)
    {
        total++;
        cout<<"第"<<total<<"条路径为: ";
        for(int i=0;i<step;i++)
            cout<<"("<<point[i].x<<","<<point[i].y<<")";
        cout<<endl;
        return;
    }
    for(int i=0;i<4;i++)
    {
        int curx=x+dx[i];
        int cury=y+dy[i];
        if(ok(curx,cury))
        {
            vis[curx][cury]=1;
            point[step].x=curx;point[step].y=cury;//记录路径
            dfs(curx,cury,step+1);
            vis[curx][cury]=0;
        }
    }
}

void bfs(int x,int y)//广搜求最短路径
{
    num[x][y]=0;
    queue<P>q;
    P a,b;
    a.x=x;
    a.y=y;
    path[a.x][a.y].fx=0;path[a.x][a.y].fy=0;
    q.push(a);
    while(!q.empty())
    {
        b=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            a.x=b.x+dx[i];
            a.y=b.y+dy[i];
            if(ok(a.x,a.y))
            {
                vis[a.x][a.y]=1;
                q.push(a);
                path[a.x][a.y].fx=dx[i];
                path[a.x][a.y].fy=dy[i];
                num[a.x][a.y]=num[b.x][b.y]+1;//记录步数
            }
        }
    }
}

void print(int x,int y)//输出最短路径
{
    if(x==sx&&y==sy)
    {
         cout<<"(1,1)";
         return;
    }
    print(x-path[x][y].fx,y-path[x][y].fy);
    cout<<"("<<x<<","<<y<<")";
}
int main()
{
    memset(vis,0,sizeof(vis));
    memset(num,0,sizeof(num));
    vis[sx][sy]=1;
    point[0].x=sx;point[0].y=sy;
    dfs(sx,sy,1);
    cout<<"总计有"<<total<<"条可到达路径"<<endl;
    memset(vis,0,sizeof(vis));
    vis[sx][sy]=1;
    bfs(sx,sy);
    cout<<"到达各个点的最少步数如下:"<<endl<<endl;
    for(int i=0;i<6;i++)
    {
        for(int j=0;j<6;j++)
            cout<<num[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl;
    cout<<"最少要走"<<num[ex][ey]<<"步才能走到出口"<<endl<<endl;;
    cout<<"其中一条最短路径为:";print(ex,ey);cout<<endl;
    return 0;
}

运行截图：