计算智能--18276 走迷宫--BFS--求最短路径长度

待我称王封你为后i 2023-07-24 09:04 11阅读 0赞

## 题目描述 ##

18276 走迷宫  
时间限制:1000MS 代码长度限制:10KB  
提交次数:0 通过次数:0

题型: 编程题 语言: G++;GCC;VC  
Description  
有一个N\*M的格子迷宫，1代表该格子为墙，不能通过，0代表可以通过，另外，在迷宫中  
有一些传送门，走到传送门的入口即会自动被传送到传送门的出口（一次传送算1步）。人在迷宫中可以尝试  
上下左右四个方向移动。现在给定一个迷宫和所有传送门的出入口，以及起点和终点，  
问最少多少步可以走出迷宫。如果不能走出迷宫输出“die”。

输入格式  
该程序为多CASE，第1行为CASE的数量  
每一个CASE，第1行为两个数N（行）和M（列）  
然后N行每行M个数  
之后是一个数W，为传送门的数量  
之后每行一个传送门的入口坐标c1(行),r1(列)和出口坐标c2,r2  
之后是起点坐标和终点坐标sc(行) sr(列) ec(行) er(列)

注：传送门出入口和起点坐标和终点坐标不会出现在墙的位置  
所有数字不超过100

输出格式  
如题

输入样例  
2  
4 3  
011  
011  
110  
110  
1  
1 0 2 2  
0 0 3 2  
2 2  
01  
10  
0  
0 0 1 1

输出样例  
3  
die

作者 admin

Version: 1

## 简单说下 ##

该题的算法如题目，BFS，这题直接用BFS模板再修改一点就差不多了。该题有几个注意的地方；  
1.可能从起点开始就有传送门。  
2.可能传送门传到自己  
3.可能传送门之间互相传送  
这几个情况做好vis标记就可以避免了。

代码如下：

#include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<queue>
    using namespace std;
    #define ll long long
    bool vis[105][105];
    char map1[105][105];
    int n,m;
    int ans[105][105];
    int xx[4]= {
        1,0,0,-1};
    int yy[4]= {
        0,1,-1,0};
    typedef struct
    {
        
        int endx,endy;
    } NODE;
    NODE map2[105][105];
    void get_map()
    {
        
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                cin>>map1[i][j];
    }
    void init()
    {
        
        for(int i=0; i<105; i++)
            for(int j=0; j<105; j++)
                vis[i][j]=0;
                for(int i=0;i<105;i++)
                    for(int j=0;j<105;j++)
                    ans[i][j]=99999999;
    }
    int main()
    {
        
        int T;
        cin>>T;
        while(T--)
        {
        
            int step=0;
            cin>>n>>m;
            get_map();
            init();
            int t;
            cin>>t;
            for(int i=0; i<t; i++)
            {
        
                int x,y,x1,y1;
                cin>>x>>y>>x1>>y1;
                map2[x][y].endx=x1;
                map2[x][y].endy=y1;
                map1[x][y]='2';
            }
            int startx,starty,endx,endy;
            cin>>startx>>starty>>endx>>endy;
            queue<int>x;
            queue<int>y;
            x.push(startx);
            y.push(starty);
            ans[startx][starty]=0;
            while(!x.empty()||!y.empty())
            {
        
                if(vis[x.front()][y.front()])
                {
        
                    x.pop();
                    y.pop();
                    continue;
                }
                if(x.front()==endx&&y.front()==endy)
                {
        
                    break;
                }
                if(map1[x.front()][y.front()]=='2')
                {
        
                    vis[x.front()][y.front()]=1;
                    x.push(map2[x.front()][y.front()].endx);
                    y.push(map2[x.front()][y.front()].endy);
                    ans[map2[x.front()][y.front()].endx][map2[x.front()][y.front()].endy]=min(ans[map2[x.front()][y.front()].endx][map2[x.front()][y.front()].endy],ans[x.front()][y.front()]+1);
                }
                else
                {
        
                    for(int i=0; i<4; i++)
                    {
        
                        int dx,dy;
                        dx=x.front()+xx[i];
                        dy=y.front()+yy[i];
                        if(!vis[dx][dy]&&dx>=0&&dx<n&&dy>=0&&dy<m&&map1[dx][dy]!='1')
                        {
        
                            vis[x.front()][y.front()]=1;
                            x.push(dx);
                            y.push(dy);
                            ans[dx][dy]=min(ans[x.front()][y.front()]+1,ans[dx][dy]);
                        }
                    }
                }
                x.pop();
                y.pop();
    
            }
            if(ans[endx][endy]==99999999)
                cout<<"die"<<'\n';
            else
                cout<<ans[endx][endy]<<'\n';
        }
    }