hdu 1253 胜利大逃亡 简单bfs

    xiaoxiao2021-03-25  256

    题意:在3维空间的最短路。 思路:直接bfs,每个状态最多有6个方向可以转移,用G++交题超时,c++交没问题 链接: http://acm.hdu.edu.cn/showproblem.php?pid=1253 #include<cstdio> #include<cstring> #include<queue> using namespace std; const int maxn = 55; int map[maxn][maxn][maxn]; int d[maxn][maxn][maxn]; int Move[]={0,0,1,0,0,-1,0,0};//x,y,z+1 x,y+1,z x+1,y,z x,y,z-1 x,y-1,z x-1,y,z int A,B,C,T; struct node { int i,j,k; node(int i,int j,int k):i(i),j(j),k(k){ } }; bool check(int i,int j,int k) { bool a=(i>=0&&i<A&&j>=0&&j<B&&k>=0&&k<C); return a; } void bfs() { queue<node> q; q.push(node(0,0,0)); d[0][0][0]=0; while(!q.empty()) { int sz = q.size(); while(sz--) { node a=q.front();q.pop(); int di,dj,dk,ci,cj,ck; di=a.i;dj=a.j;dk=a.k; if(di==A-1&&dj==B-1&&dk==C-1)return; for(int i=0;i<6;i++) { ci=di+Move[i]; cj=dj+Move[i+1]; ck=dk+Move[i+2]; if(check(ci,cj,ck)&&d[ci][cj][ck]==-1&&map[ci][cj][ck]==0) { d[ci][cj][ck]=d[di][dj][dk]+1; q.push(node(ci,cj,ck)); } } } } } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d%d%d",&A,&B,&C,&T); memset(d,-1,sizeof(d)); for(int i=0;i<A;i++) for(int j=0;j<B;j++) for(int k=0;k<C;k++) scanf("%d",&map[i][j][k]); bfs(); if(d[A-1][B-1][C-1]>T||d[A-1][B-1][C-1]==-1) printf("-1\n"); else printf("%d\n",d[A-1][B-1][C-1]); } }
    转载请注明原文地址: https://ju.6miu.com/read-168.html

    最新回复(0)