hdoj 2102 A计画【BFS】

意甲冠军：文的就不说了。求救出公主所须要的最短时间，所以用广搜。

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

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

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

！

#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;

}

A计画

hdoj 2102 A计画 【BFS】

hdoj 2102 A计画【BFS】