（C++）POJ-3984——走迷宫（广度优先算法）

r囧r小猫 2021-12-01 12:46 231阅读 0赞

### 题目描述 ###

地图显示，法阵是方形的，纵横皆为五里，在地图上简示为5\*5的矩阵，且只由0或1组成。其中，0表示可以走的路，1表示阻止通行的屏障。左上角和右下角分别是阵的入口和出口，这两个位置的数字保证为0。  
既然得到了地图，破解法阵自然不再是难事。现在，小胖不仅想要走出法阵，还想知道怎样才能用最短的路线走出法阵。

#### *input* ####

输入是一个5 × 5的二维数组，仅由0、1两数字组成，表示法阵地图。

#### *output* ####

输出若干行，表示从左上角到右下角的最短路径依次经过的坐标，格式如样例所示。数据保证有唯一解。

### 题目讲解 ###

很明显，这道题需要使用到广度优先搜索（BFS）来找到一条最短路径，唯一需要注意的一点是题目要求输出这条路径，而不是这条路径的长度，所以我们可以采用一个结构体数组 parent\[N\]\[N\] 来保存所走路径中每一个点的前一个点。  
这样的话，如果我们按题目来从起点到终点，那么要输出路径的则需要反向输出，所以为了方便起见，我们从终点开始搜索，搜索到起点，这样我们就可以直接得到正确的路径

### 源代码（可AC） ###

#include<iostream>
    #include<queue>
    #include<cstring>
    using namespace std;
    int g[7][7];
    int visit[7][7];
    struct Point
    {
        
        int x;
        int y;
        Point(){
        };//无参数的构造函数
        Point(int _x,int _y):x(_x),y(_y){
        };//函数参数的构造函数
    };
    Point parent[7][7];
    bool bfs(Point &pb,Point &pe)
    {
        
        queue<Point> que;
        int run[][2]={
        
        {
        0,-1},{
        0,1},{
        1,0},{
        -1,0}
        };  //行走方向数组
        parent[pb.x][pb.y]=pb;//父节点记录数组
        que.push(pb);
        while(!que.empty())
        {
        
            Point temp=que.front();//如果走到终点则返回true
            que.pop();
            visit[temp.x][temp.y]=1;
            if(temp.x==pe.x&&temp.y==pe.y)
                return true;
            for(int i=0;i<4;++i)
            {
        
                Point temp2(temp.x+run[i][0],temp.y+run[i][1]);
                if(g[temp2.x][temp2.y]==0&&visit[temp2.x][temp2.y]==0)
                {
        
                    que.push(temp2);//将可行走的路径放入队列中
                    parent[temp2.x][temp2.y]=temp;//记录该路口的前一个路口
                }
    
            }
        }
        return false;
    }
    int main()
    {
        
        for(int i=0;i<7;++i)
            g[0][i]=1;
        for(int i=0;i<7;++i)
            g[i][0]=1;
        for(int i=0;i<7;++i)
            g[6][i]=1;
        for(int i=0;i<7;++i)
            g[i][6]=1;
        while(cin>>g[1][1])
        {
        
            memset(visit,0,sizeof(visit));
            for(int i=1;i<=5;++i)
                for(int j=1;j<=5;++j)
            {
        
                if(i==1&&j==1)
                    continue;
                else
                    cin>>g[i][j];
            }
            Point g_begin(1,1),g_end(5,5);
            if(bfs(g_end,g_begin))
            {
        
                Point a(1,1);
                cout<<"(0, 0)"<<endl;
                while(a.x!=5||a.y!=5)
                {
        
                    a=parent[a.x][a.y];
                    cout<<'('<<a.x-1<<", "<<a.y-1<<')'<<endl;
    
                }
            }
            /*if(bfs(g_begin,g_end))
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;*/
        }
    }