首页 > 代码库 > hdu2102(bfs)
hdu2102(bfs)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2102
分析:bfs求最短时间到达‘P‘点,不过本题有好几个trick,我都踩到了,自己还是太嫩了。。。
注意:可能两层同个位置都是‘#‘,还有经过‘#‘时只能被传送,不能经过它上下左右移动。。。
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 100010using namespace std;int n,m,t;char s[2][15][15];struct node{ int x,y,z,step; bool operator<(const node &a)const { return step>a.step; }};int dx[]={1,-1,0,0,0,0};int dy[]={0,0,1,-1,0,0};int dz[]={0,0,0,0,1,-1};int vis[2][15][15],flag;node make_node(int a,int b,int c,int d){ node temp; temp.x=a;temp.y=b; temp.z=c;temp.step=d; return temp;}int judge(int a,int b,int c){ return a>=0&&a<2&&b>=0&&b<n&&c>=0&&c<m&&!vis[a][b][c]&&s[a][b][c]!=‘*‘;}void bfs(int xx,int yy,int zz){ priority_queue<node>que; while(!que.empty())que.pop(); memset(vis,0,sizeof(vis)); node cur,nxt; vis[xx][yy][zz]=1; que.push(make_node(xx,yy,zz,0)); while(!que.empty()) { cur=que.top();que.pop();//进入队列的step不同步时,最好用优先队列保证最小步数出队 if(s[cur.x][cur.y][cur.z]==‘P‘) { if(cur.step<=t)flag=1; return ; } for(int i=0;i<6;i++) { int x=cur.x+dx[i],y=cur.y+dy[i],z=cur.z+dz[i]; if(judge(x,y,z)) { if(dx[i]&&s[cur.x][cur.y][cur.z]!=‘#‘)continue;//该位置可传送 if(dx[i]&&s[x][y][z]==‘#‘)continue;//两边都是传送机 if(s[cur.x][cur.y][cur.z]==‘#‘&&!dx[i])continue;//这里被坑了好久,不能左右上下移动了 vis[x][y][z]=1; if(dx[i]) que.push(make_node(x,y,z,cur.step)); else que.push(make_node(x,y,z,cur.step+1)); } } }}int main(){ int x,y,z,cas; scanf("%d",&cas); while(cas--) { scanf("%d%d%d",&n,&m,&t); for(int i=0;i<=1;i++) { for(int j=0;j<n;j++) { scanf("%s",s[i][j]); } } flag=0; bfs(0,0,0); if(flag)puts("YES"); else puts("NO"); }}
hdu2102(bfs)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。