题目链接：

pid=2102">http://acm.hdu.edu.cn/showproblem.php?pid=2102

这道题属于BFS+优先队列

開始看到四分之中的一个的AC率感觉有点吓人，后来一做感觉就是模板改了点东西而已，一遍就AC了，只是在主函数和全局变量里面都定义了n和m导致我白白浪费了debug的时间。

果然全局变量得小心用啊。

跟模板一样的，定义一个结构体，仅仅只是多加了个參数，就是迷宫的层数，我用0代表第一层。1代表第二层，这在数组里面会体现的。

struct node {

    int index;//层数

    int x,y;//坐标

    int time;

    friend bool operator <(const node &a,const node &b){

    //时间少的放在队列前面

        return a.time>b.time;

    }

};

我定义的那个map是

char map[2][11][11];

map[层数][x][y]这种。

还有个can_go 函数检測当前点是否可走：

int can_go(int index,int x,int y){

   if(x<0||x>=n||y<0||y>=m||map[index][x][y]=='*'){

    return 0;

   }

   return 1;

}

我大概就讲一下跟模板题有啥不同吧。

这道题里面会遇到传送门’#’仅仅要遇到就把当前层格子标记为已经过vis[index][x][y]=1之后立刻飞到还有一层即可了，注意，若还有一层是墙那就挂了，说明这里不能走，直接continue换个方向继续。或者还有一层同一位置也是传送门’#’那也不行，也continue即可了

if(map[!next.index][next.x][next.y]=='*'||

<span style="white-space:pre">	</span>map[!next.index][next.x][next.y]=='#'){

<span style="white-space:pre">	</span>continue;

}

之后仅仅要队列不为空。就取出队列的头节点，推断是否为终点，假设是，则返回到达当前节点所需时间即:now.time；若不是，那接下来把now的四个方向所有遍历一遍。假设遍历到达不是墙就将其增加队列。而且把当前time更新：next.time=now.time+1。一直循环直到que.top出来的坐标代表的是终点为止。

贴个代码：

#include <iostream>

#include <cstring>

#include <cstdio>

#include <queue>

using namespace std;

char map[2][11][11];

int vis[2][11][11];

int t,n,m;

int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

struct node {

    int index;//层数

    int x,y;//坐标

    int time;

    friend bool operator <(const node &a,const node &b){

    //时间少的放在队列前面

        return a.time>b.time;

    }

};

int can_go(int index,int x,int y){

   if(x<0||x>=n||y<0||y>=m||map[index][x][y]=='*'){

    return 0;

   }

   return 1;

}

//bfs若time > T 则返回 -1

int bfs(int index,int x,int y){

    priority_queue<node>que;

    int i;

    node now,next;

    memset(vis,0,sizeof(vis));

    now.index=index;

    now.x=x;

    now.y=y;

    now.time=0;

    vis[index][x][y]=1;

    que.push(now);

    while(!que.empty()){

        now=que.top();

        que.pop();

        if(now.time>t){

            return -1;

        }

        if(map[now.index][now.x][now.y]=='P'){

            return 1;

        }

        for(i=0;i<4;i++){

            next.index=now.index;

            next.x=now.x+dir[i][0];

            next.y=now.y+dir[i][1];

            if(!vis[next.index][next.x][next.y] && can_go(next.index,next.x,next.y)){

                vis[next.index][next.x][next.y]=1;

                if(map[next.index][next.x][next.y]=='#'&&!vis[!next.index][next.x][next.y]){

                    if(map[!next.index][next.x][next.y]=='*'||

                       map[!next.index][next.x][next.y]=='#'){

                        continue;

                    }

                    next.index=!next.index;

                    vis[next.index][next.x][next.y]=1;

                    next.time=now.time+1;

                    que.push(next);

                }

                else {

                    next.time=now.time+1;

                    que.push(next);

                }

            }

        }

    }

    return -1;

}

int main()

{

    int ans;

    int i;

    int c;

    scanf("%d",&c);

    while(c--){

        scanf("%d%d%d",&n,&m,&t);

        //printf("%d%d%d",n,m,t);

        for(i=0;i<n;i++){

            scanf("%s",map[0][i]);

        }

        for(i=0;i<n;i++){

            scanf("%s",map[1][i]);

        }

        ans=bfs(0,0,0);

        if(ans==-1){

            printf("NO\n");

        }

        else printf("YES\n");

    }

    return 0;

}