一道三维BFS题,以前做过一次三维BFS,那次WA出了翔,这次我怀着一次AC的心态小心翼翼的做着,结果这回TLE出翔了。
结果是题面上说要用C++交,G++交会超时。。。我看题时看到了,提交时却给忘了,并且还在想剪枝往里面添,各种TLE。
发现TLE的错误原因后又交了一发WA,发现是我BFS里在while(!q.empty())结束后没有返回语句,加上之后AC了,贴代码吧
#include<iostream> #include<algorithm> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<vector> #include<set> #include<queue> #include<stack> #include<stdlib.h> #include<ctime> #define PI acos(-1) using namespace std; int a,b,c,t; int visit[55][55][55]; int dir[6][3]={1,0,0,-1,0,0,0,1,0,0,-1,0,0,0,1,0,0,-1}; int map[55][55][55]; int bfs() { int x,y,z,step,nextstep,xt,yt,zt,i; queue<int>q; q.push(0); //放入x q.push(0); //放入y q.push(0); //放入z q.push(0); //放入step; visit[0][0][0]=1; while(!q.empty()) { x=q.front(); q.pop(); y=q.front(); q.pop(); z=q.front(); q.pop(); step=q.front(); q.pop(); if(x==a-1&&y==b-1&&z==c-1) { if(step<=t) return step; else return -1; } for(i=0;i<6;i++) { xt=x+dir[i][0]; yt=y+dir[i][1]; zt=z+dir[i][2]; nextstep=step+1; if(!visit[xt][yt][zt]&&!map[xt][yt][zt]&&xt>=0&&xt<a&&yt>=0&&yt<b&&zt>=0&&zt<c) { q.push(xt); q.push(yt); q.push(zt); q.push(nextstep); visit[xt][yt][zt]=1; } } } return -1; } int main() { int i,j,k,n,x; scanf("%d",&n); while(n--) { memset(visit,0,sizeof(visit)); scanf("%d%d%d%d",&a,&b,&c,&t); for(i=0;i<a;i++) for(j=0;j<b;j++) for(k=0;k<c;k++) scanf("%d",&map[i][j][k]); printf("%d\n",bfs()); } return 0; }