HDU 1253

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 int x,y,z,t,tx,ty,tz;
 5 const int qq=60+5,no=1e7;
 6 int map[qq][qq][qq],dis[qq][qq][qq];
 7 int minx;
 8 int dir[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
 9 void dfs(int sz,int sy,int sx,int cnt)
10 {
11     if(sz<0||sy<0||sx<0||sz>=z||sy>=y||sx>=x)return;
12     if(map[sz][sy][sx]==1)    return;
13     if(cnt>=dis[sz][sy][sx])return;
14     if((t-cnt)<abs(sz-tz)+abs(sy-ty)+abs(sx-tx))    return;    //这一点必须比较，不比较就会超时 
15     if(cnt>=minx)    return;
16     if((t-cnt)<0)    return;
17     if(sz==tz&&sy==ty&&sx==tx)    if(cnt<minx)    minx=cnt;
18     dis[sz][sy][sx]=cnt;
19     for(int i=0;i<6;++i)
20     dfs(sz+dir[i][0],sy+dir[i][1],sx+dir[i][2],cnt+1);
21     return;
22 }
23 int main()
24 {
25     int k;scanf("%d",&k);
26     while(k--){
27         int wall=0;
28         scanf("%d%d%d%d",&z,&y,&x,&t);
29         for(int i,j,k=0;k<z;++k)
30             for(i=0;i<y;++i)
31                 for(j=0;j<x;++j){
32                     scanf("%d",&map[k][i][j]);
33                     dis[k][i][j]=no;
34                     if(map[k][i][j]==1)    ++wall;
35                 }
36         minx=no;
37         tx=x-1;ty=y-1;tz=z-1;
38         if(t<tx+ty+tz){
39             printf("-1\n");
40             continue;
41         }
42         map[0][0][0]=0;
43         dfs(0,0,0,0);
44         if(minx==no)    printf("-1\n");
45         else            printf("%d\n",minx);
46     }
47 }