BFS+剪枝
不剪枝直接TLE了呀，无语，剪枝真是一门学问，果然，搜索最重要的是剪枝
#include<iostream> #include<queue> #include<string> #include<algorithm> using namespace std; int map[51][51][51],vis[51][51][51],a,b,c,mins,T,count1; int dir[6][3]={{0,1,0},{0,-1,0},{1,0,0},{-1,0,0},{0,0,1},{0,0,-1}}; bool escape; struct node { int x,y,z,dis; node(int _x=0,int _y=0,int _z=0,int _dis=0):x(_x),y(_y),z(_z),dis(_dis){}; }; void bfs() { node f; queue<node> q; f.x=f.y=f.z=1; f.dis=0; q.push(f); vis[1][1][1]=1; while(!q.empty()) { node t=q.front(); q.pop(); if(t.x==a&&t.y==b&&t.z==c&&t.dis<=T) { mins=t.dis; escape=1; return ; } if(t.dis>T) return; for(int l=0;l<6;l++) { int i=t.x+dir[l][0]; int j=t.y+dir[l][1]; int k=t.z+dir[l][2]; if(i<=a&&i>0&&j<=b&&j>0&&k<=c&&k>0 &&!vis[i][j][k]&&map[i][j][k]!=1) { vis[i][j][k]=1; if(t.dis+1+a-i+b-j+c-k>T)//已花时间+之后的最短路径要比总时间短 continue; q.push(node(i,j,k,t.dis+1)); } } } } int main() { int cas; scanf("%d",&cas); while(cas--) { count1=0; scanf("%d %d %d %d",&a,&b,&c,&T); for(int i=1;i<=a;i++) for(int j=1;j<=b;j++) for(int k=1;k<=c;k++) { scanf("%d",&map[i][j][k]); if(map[i][j][k]!=0) count1++; vis[i][j][k]=0; } escape=0; if(a*b*c-count1<a+b+c-2|| T<a+b+c) //这个好理解，可走路径长至少要比最短路径长，而且最短路径一定要比总时间长 cout<<-1<<endl; else { bfs(); if(escape) cout<<mins<<endl; else cout<<-1<<endl; } } return 0; }转载于:https://www.cnblogs.com/nanke/archive/2011/08/01/2123778.html
相关资源：数据结构—成绩单生成器