题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1253
题意：三维BFS，不解释
题解：DFS+剪枝会超时，裸BFS会超时，BFS+剪枝才能AC，有点伤，我以为数据会让DFS速度快一下，看来是我天真了
1 #include<cstdio> 2 #include<queue> 3 using namespace std; 4 #define FFC(i,a,b) for(int i=a;i<=b;i++) 5 int g[51][51][51],a,b,c,ti,ok,ts,dir[6][3]={0,0,1,0,0,-1,0,1,0,0,-1,0,1,0,0,-1,0,0}; 6 bool v[51][51][51]; 7 struct dt{int x,y,z,time;}; 8 bool check(int x,int y,int z,int tt){ 9 if(v[x][y][z]||g[x][y][z]||x<1||x>a||y<1||y>b||z<1||z>c||tt>ti)return 0; 10 else if(a+b+c-x-y-z+tt>ti)return 0;//剪枝 11 return 1; 12 } 13 void fuck(){ 14 dt s,now;s.x=1,s.y=1,s.z=1,s.time=0; 15 queue<dt>Q;Q.push(s); 16 while(!Q.empty()){ 17 now=Q.front();Q.pop(); 18 if(now.x==a&&now.y==b&&now.z==c){ok=now.time;return;} 19 for(int i=0;i<6&&ok==-1;i++){ 20 int xx=now.x+dir[i][0],yy=now.y+dir[i][1],zz=now.z+dir[i][2]; 21 if(!check(xx,yy,zz,now.time+1))continue; 22 s.x=xx,s.y=yy,s.z=zz,s.time=now.time+1,v[xx][yy][zz]=1; 23 Q.push(s); 24 } 25 } 26 } 27 int main(){ 28 scanf("%d",&ts); 29 while(ts--){ 30 scanf("%d%d%d%d",&a,&b,&c,&ti);ok=-1; 31 FFC(i,1,a)FFC(j,1,b)FFC(k,1,c){scanf("%d",&g[i][j][k]);v[i][j][k]=0;} 32 fuck(); 33 printf("%d ",ok); 34 } 35 return 0; 36 }