题目链接：?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 则返回 -1int 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;}
版权声明：欢迎转载，转载时请在文章开头注明出处
最有效的资本是我们的信誉，它24小时不停为我们工作。
