首页 > 代码库 > hdu 1253 胜利大逃亡(bfs)
hdu 1253 胜利大逃亡(bfs)
胜利大逃亡
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 20468 Accepted Submission(s): 8152
题意给出一个长宽高为A,B,C,三维的地图要求在规定时间内从(0,0,0,)走到(A-1,B-1,C-1)
三维bfs 模板题不多讲注意对应好坐标就行
#include<iostream> #include<cstdio> #include<cstring> #include<stack> #include<queue> #include<algorithm> using namespace std; int d[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}}; int n,m,h,T; int map[55][55][55]; int vis[55][55][55]; struct node{ int x,y,z; int depth;//记录所用时间 }; bool jud(int x,int y,int z) { if(x<0||x>=h||y<0||y>=n||z<0||z>=m) return false; if(vis[x][y][z]) return false; if(map[x][y][z]==1) return false; return true; } int bfs(int t,int x,int y) { int i,j,k; queue<node> q; node a,b,c; a.z=t; a.x=x; a.y=y; a.depth=0; q.push(a); vis[0][0][0]=1; while(!q.empty()) { b=q.front(); q.pop(); if(b.z==h-1&&b.x==n-1&&b.y==m-1) return b.depth; for(i=0;i<6;i++) { c.x=b.x+d[i][0]; c.y=b.y+d[i][1]; c.z=b.z+d[i][2]; if(!jud(c.z,c.x,c.y)) continue; vis[c.z][c.x][c.y]=1; c.depth=b.depth+1; if(c.z==h-1&&c.x==n-1&&c.y==m-1) return c.depth; q.push(c); } } return -1; } int main() { int cas,i,j,k,ans; scanf("%d",&cas); while(cas--) { scanf("%d%d%d%d",&h,&n,&m,&T); memset(vis,0,sizeof(vis)); for(i=0;i<h;i++) for(j=0;j<n;j++) for(k=0;k<m;k++) { scanf("%d",&map[i][j][k]); } if(map[h-1][n-1][m-1]==1 ||h+n+m-3>T) { printf("-1\n"); continue; } ans=bfs(0,0,0); if(ans<=T) printf("%d\n",ans); else printf("-1\n"); } return 0; }
hdu 1253 胜利大逃亡(bfs)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。