hdu 1253:胜利大逃亡（基础广搜BFS） 胜利大逃亡

 1 #include <iostream>
 2 #include <string.h>
 3 #include <queue> 
 4 using namespace std;
 5 int a[55][55][55];    //记录地图
 6 int isv[55][55][55];    //记录访问过没有 
 7 int dx[6] = {0,1,0,-1,0,0};
 8 int dy[6] = {1,0,-1,0,0,0}; 
 9 int dz[6] = {0,0,0,0,-1,1};
10 int A,B,C,T;
11 struct NODE{
12     int x;
13     int y;
14     int z;
15     int step;
16 };
17 bool judge(int x,int y,int z,int step)
18 {
19     if( x<1 || y<1 || z<1 || x>A || y>B || z>C )    //出界 
20         return 1;
21     if( isv[x][y][z] )    //走过 
22         return 1;
23     if( a[x][y][z]==1 )    //遇到墙 
24         return 1;
25     if(step+1>T)    //如果走这一步超过了时间，不能走
26         return 1;
27     return 0;
28 }
29 int bfs(int x,int y,int z)    //返回到达终点的时间 
30 {
31     memset(isv,0,sizeof(isv));
32     queue <NODE> q;
33     NODE cur,next;
34     cur.x = x;
35     cur.y = y;
36     cur.z = z;
37     cur.step = 0;
38     isv[1][1][1] = true;
39     q.push(cur);    //第一个节点入队 
40     while(!q.empty()){
41         cur = q.front();
42         q.pop();    //队首出队
43         if( cur.x==A && cur.y==B && cur.z==C){
44             return cur.step;
45         }
46         for(int i=0;i<6;i++){
47             int nx = cur.x + dx[i];
48             int ny = cur.y + dy[i];
49             int nz = cur.z + dz[i];
50             if(judge(nx,ny,nz,cur.step))    //判定    
51                 continue;
52             //可以走
53             next.x = nx;
54             next.y = ny;
55             next.z = nz;
56             isv[nx][ny][nz] = true;    //记录访问过 
57             next.step = cur.step + 1; 
58             q.push(next);
59         } 
60     }
61     return 0;
62 }
63 int main()
64 {
65     int n;
66     cin>>n;
67     while(n--){
68         scanf("%d%d%d%d",&A,&B,&C,&T);
69         int i,j,k;
70         for(i=1;i<=A;i++)
71             for(j=1;j<=B;j++)
72                 for(k=1;k<=C;k++)
73                     scanf("%d",&a[i][j][k]);
74         int step = bfs(1,1,1);
75         if(step)    //到达终点
76             printf("%d
",step);
77         else
78             printf("-1
");
79     }
80     return 0;
81 }