首页 > 代码库 > HDU 1072 Nightmare (BFS)
HDU 1072 Nightmare (BFS)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1072
题目大意:
走迷宫,初始剩余时间为6min,每步1min;到reset区是若剩余时间大于0,则可以重置。到终点3区,若时间大于0,则成功逃脱。(可以走回路)
0:wall
1:可以走
2:起点
3:终点
4:剩余时间重置为6
源代码:
#include<iostream> #include<cstring> #include<cstdio> #include<queue> #define maxn 1001 using namespace std; int go[4][2] = { {-1,0} , {1,0} , {0,-1} , {0,1}}; int s,n,m; struct node{ int x,y; int pos; int time; int rest; }p[maxn*maxn]; int BFS() { //cout<<s<<endl; node next; queue<node> que; que.push(p[s]); while(!que.empty()) { for(int i=0;i<4;i++) { int x=que.front().x+go[i][0]; int y=que.front().y+go[i][1]; if(x>0&&x<=n&&y>0&&y<=m&&p[(x-1)*m+y].pos!=0&&que.front().rest>1) { //cout<<p[(x-1)*n+y].pos<<"--->\n"; if(p[(x-1)*m+y].pos==3) return que.front().time+1; else { if(p[(x-1)*m+y].pos==4) { next.rest=6; p[(x-1)*m+y].pos=0; } else next.rest=que.front().rest-1; next.time=que.front().time+1; next.x=x; next.y=y; que.push(next); } } } que.pop(); } return -1; } int main() { int t; scanf("%d",&t); while(t--) { int v,num; num=0; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&v); p[++num].pos=v; p[num].x=i; p[num].y=j; p[num].time=0; p[num].rest=0; if(v==2) { s=num; p[num].rest=6; } } printf("%d\n",BFS()); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。