SCAU--计算智能--走迷宫2--BFS

Dear 丶 2023-07-25 14:02 17阅读 0赞

1 走迷宫2  
Time Limit:1000MS Memory Limit:65535K  
题型: 编程题 语言: 无限制  
描述  
有一个N\*M(N,M<=10)的格子迷宫，1代表该格子为墙，不能通过，0代表可以通过，人在迷宫中可以尝试上下左右四个方向移动。  
另外，在迷宫中如果从左边走出迷宫会回到迷宫最右边一格（只要该格不是墙），行不变，同样，从右边走出迷宫会  
回到迷宫最左边一格，向上走出迷宫会回到迷宫最下边一格，向下走出迷宫会回到迷宫最上边一格。  
现在给定一个迷宫，以及起点和终点，问最少多少步可以走出迷宫。如果不能走出迷宫输出“die”。

输入格式  
该程序为多CASE，第1行为CASE的数量  
每一个CASE，第1行为两个数N（行）和M（列）  
然后N行每行M个数，之后是起点坐标和终点坐标sc(行) sr(列) ec(行) er(列)  
输出格式  
如题  
输入样例  
2  
4 3  
011  
010  
110  
110  
0 0 3 2  
2 2  
01  
10  
0 0 1 1  
输出样例  
4  
die  
提示  
第一个case，可以从（1，0）走到（1，2）  
作者 admin

## 简单说下 ##

这题我不是套用老师给的那个代码，我是自己写的，这题就直接BFS就好，用一个数组map2存取最短路径长度。剩下的都是BFS的套路了，就不多说了。要注意初始化的问题。

代码如下：

#include<iostream>
    #include<cmath>
    #include<algorithm>
    #include<queue>
    using namespace std;
    #define INF 0x7fffffff
    char map1[15][15];
    int map2[15][15];
    bool vis[15][15];
    int xx[4]= {
        0,1,-1,0};
    int yy[4]= {
        1,0,0,-1};
    int main()
    {
        
        int T;
        cin>>T;
        while(T--)
        {
        
            int n,m;
            cin>>n>>m;
            for(int i=1; i<=n; i++)
                for(int j=1; j<=m; j++)
                {
        
                    cin>>map1[i][j];
                    map2[i][j]=INF;
                    vis[i][j]=0;
                }
            queue<int>x;
            queue<int>y;
            int beginx,beginy,endx,endy;
            cin>>beginx>>beginy>>endx>>endy;
            beginx++;
            beginy++;
            endx++;
            endy++;
            map2[beginx][beginy]=0;
            x.push(beginx);
            y.push(beginy);
            while(!x.empty())
            {
        
                if(x.front()==endx&&y.front()==endy)
                    break;
                for(int i=0; i<4; i++)
                {
        
                    int dx,dy;
                    dx=x.front()+xx[i];
                    dy=y.front()+yy[i];
                    if(dx==0)
                        dx=n;
                    else if(dx==n+1)
                        dx=1;
                    if(dy==0)
                        dy=m;
                    else if(dy==m+1)
                        dy=1;
                    if(dx>=1&&dy>=1&&dx<=n&&dy<=m&&map1[dx][dy]!='1'&&!vis[dx][dy])
                    {
        
                        vis[x.front()][y.front()]=1;
                        x.push(dx);
                        y.push(dy);
                        map2[dx][dy]=min(map2[x.front()][y.front()]+1,map2[dx][dy]);
                    }
                }
                x.pop();
                y.pop();
            }
            if(map2[endx][endy]!=INF)
                cout<<map2[endx][endy]<<'\n';
            else
                cout<<"die"<<'\n';
        }
        return 0;
    }