bfs 胜利大逃亡

 1 #include<iostream>
 2 #include<queue>
 3 #include<cstdio>
 4 
 5 using namespace std;
 6 
 7 int a,b,c,t;
 8 int map[52][52][52];
 9 int dir[6][3]={1,0,0,-1,0,0,0,1,0,0,-1,0,0,0,1,0,0,-1};
10 
11 struct node{
12     int x,y,z;
13     int step;
14 };
15 
16 int bfs(){
17     node cur,next;
18     queue<node> q;
19     cur.x = 1;
20     cur.y = 1;
21     cur.z = 1;
22     cur.step = 0;
23     map[1][1][1] = 1;
24     q.push(cur);
25     while(!q.empty()){
26         cur = q.front();
27         q.pop();
28         if(cur.step<=t && cur.x==a && cur.y == b && cur.z == c)
29             return cur.step;
30         for(int i =0;i<6;i++){
31             int cc = cur.z + dir[i][2];
32             int bb = cur.y + dir[i][1];
33             int aa = cur.x + dir[i][0];
34             if(aa>0 && aa<=a && bb>0 && bb<=b && cc>0 && cc<=c && !map[aa][bb][cc]){
35                 map[aa][bb][cc] = 1;
36                 next.x = aa;
37                 next.y = bb;
38                 next.z = cc;
39                 next.step = cur.step+1;
40                 q.push(next);
41             }
42         }
43     }
44     return -1;
45 }
46 
47 int main(){
48     int k;
49     cin>>k;
50     while(k--){
51         cin>>a>>b>>c>>t;
52         for(int i=1;i<=a;i++)
53             for(int j=1;j<=b;j++)
54                 for(int s=1;s<=c;s++)
55                     scanf("%d",&map[i][j][s]);
56         if(a+b+c>t){
57             cout<<"-1"<<endl;
58             continue;
59         }
60         cout<<bfs()<<endl;
61     }
62     return 0;
63 }