hdoj 2102 A计划【BFS】

川长思鸟来 2022-08-11 19:59 148阅读 0赞

题目：hdoj 2102 A计划[点击打开链接][Link 1]

题意：中文的就不说了。求救出公主所需要的最短时间，所以用广搜。

分析：读题之后不难做，比一般的题目多了一个条件就是可以传送，那么我们可以在广搜里面加一个传送的条件就好了。

其次这个题目注意有个坑就是如果两边都是传送门的话也不行

还有注意广搜写法，如果把队列定义成全局的话注意清空！！

#include <cstdio>
    #include <iostream>
    #include <queue>
    #include <cstring>
    #include <algorithm>
    #include <stack>
    #include <vector>
    #include <utility>
    #include <cmath>
    using namespace std;
    const int N = 20;
    int n,m,t;
    char mp[3][N][N];
    int vis[3][N][N];
    int tx[5]={0,0,1,-1};
    int ty[5]={1,-1,0,0};
    struct Node
    {
        int x,y,z;
        int step;
    };
    queue<Node> q;
    int BFS(Node st,Node en)
    {
        vis[st.x][st.y][st.z]=1;
        q.push(st);
        while(!q.empty())
        {
            Node tmp=q.front(),cpp;
            q.pop();
            if(tmp.x==en.x && tmp.y==en.y && tmp.z==en.z){
                return tmp.step;
            }
            //printf("--%d %d %d %c\n",tmp.x,tmp.y,tmp.z,mp[tmp.x][tmp.y][tmp.z]);
            if(mp[tmp.x][tmp.y][tmp.z]=='#')
            {
                cpp.x=(tmp.x+1)%2;
                cpp.y=tmp.y;
                cpp.z=tmp.z;
                if(vis[cpp.x][cpp.y][cpp.z]==1)
                    continue;
                if(mp[cpp.x][cpp.y][cpp.z]=='*' || mp[cpp.x][cpp.y][cpp.z]=='#')
                    continue;
                q.push(cpp);
                vis[cpp.x][cpp.y][cpp.z]=1;
            }
            else
            {
                for(int i=0;i<4;i++)
                {
                    cpp.x=tmp.x;
                    cpp.y=tmp.y+tx[i];
                    cpp.z=tmp.z+ty[i];
                    cpp.step=tmp.step+1;
                    if(mp[cpp.x][cpp.y][cpp.z]=='*')
                        continue;
                    if(cpp.y>=0 && cpp.z>=0 && cpp.y<n && cpp.z<m && vis[cpp.x][cpp.y][cpp.z]==0)
                    {
                        q.push(cpp);
                        vis[cpp.x][cpp.y][cpp.z]=1;
                    }
                }
            }
        }
        return -1;
    }
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int T;
        scanf("%d",&T);
        while(T--)
        {
            memset(vis,0,sizeof(vis));
            Node st,en;
            st.x=0,st.y=0,st.step=0,st.z=0;
            scanf("%d%d%d",&n,&m,&t);
            for(int k=0;k<2;k++)
                for(int i=0;i<n;i++)
                    for(int j=0;j<m;j++){
                        cin>>mp[k][i][j];
                        if(mp[k][i][j]=='P')
                            en.x=k,en.y=i,en.z=j;
                    }
            //cout<<en.x<<" "<<en.y<<" "<<en.z<<endl;
            int ans=BFS(st,en);
            if(ans<=t && ans!=-1)
                puts("YES");
            else
                puts("NO");
            while(!q.empty())  //注意这里
                q.pop();
        }
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=2102