1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <queue> 6 #include <cmath> 7 using namespace std; 8  9 struct Point10 {11     int x, y, z;12     int steps;13 }start;14 15 int a, b, c, m;16 int map[52][52][52];17 int dir[6][3] = {{1,0,0}, {-1,0,0}, {0,1,0}, {0,-1,0}, {0,0,1}, {0,0,-1}};18 19 bool islegal(int x, int y, int z)20 {21     return (x>=0 && x<a && y>=0 && y<b && z>=0 && z<c && (map[x][y][z] == 0));22 }23 24 void BFS(void)25 {26     queue<Point> qu;27     start.x = start.y = start.z = start.steps = 0;28     map[0][0][0] = 1;29     qu.push(start);30     while(!qu.empty())31     {32         Point fir = qu.front();33         qu.pop();34         if(fir.x==a-1 && fir.y==b-1 && fir.z==c-1)35             {printf("%d\n", fir.steps);    return;}36         if(fir.steps > m)37             {printf("-1\n");    return;}38         for(int i = 0; i < 6; ++i)39         {40             int xx = fir.x + dir[i][0];41             int yy = fir.y + dir[i][1];42             int zz = fir.z + dir[i][2];43             if(islegal(xx, yy, zz))44             {45                 Point next;46                 next.x = xx, next.y = yy, next.z = zz;47                 next.steps = fir.steps + 1;48                 map[zz][xx][yy] = 1;49                 if(abs(xx-a+1)+abs(yy-b+1)+abs(zz-c+1)+next.steps > m)50                     continue;51                 qu.push(next);52             }53         }54     }55     printf("-1\n");56 }57 58 int main(void)59 {60     #ifdef LOCAL61         freopen("1253in.txt", "r", stdin);62     #endif63 64     int T;65     scanf("%d", &T);66     while(T--)67     {68         scanf("%d%d%d%d", &a, &b, &c, &m);69         for(int i = 0; i < a; ++i)70             for(int j = 0; j < b; ++j)71                 for(int k = 0; k < c; ++k)72                     scanf("%d", &map[i][j][k]);73 74         BFS();75     }76     return 0;77 }