http://acm.hdu.edu.cn/showproblem.php?pid=1253
View Code
1 #include<stdio.h> 2 #include<iostream> 3 using namespace std ; 4 #include<queue> 5 const int INF=10000 ; 6 const int MAX=70 ; 7 int a, b, c, t ; 8 struct node 9 { 10 int x, y, z ; 11 int time ; 12 } ; 13 14 int dir[6][3]={{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}} ; 15 int map[MAX][MAX][MAX] ; 16 int curtime[MAX][MAX][MAX] ; 17 int bfs(node s) 18 { 19 int i ; 20 queue<node>Q ; 21 Q.push(s) ; 22 node head ; 23 while(!Q.empty()) 24 { 25 head = Q.front() ; 26 Q.pop() ; 27 for(i=0; i<6; i++) 28 { 29 int x = head.x + dir[i][0] ; 30 int y = head.y + dir[i][1] ; 31 int z = head.z + dir[i][2] ; 32 if(x>=0&&x<=a-1&&y>=0&&y<=b-1&&z>=0&&z<=c-1&&map[x][y][z]!=1) 33 { 34 node t ; 35 t.x = x ; 36 t.y = y ; 37 t.z = z ; 38 t.time = head.time + 1 ; 39 if(t.time<curtime[x][y][z]) 40 { 41 curtime[x][y][z] = t.time ; 42 Q.push(t) ; 43 } 44 } 45 } 46 } 47 return curtime[a-1][b-1][c-1] ; 48 } 49 int main() 50 { 51 int k ; 52 node start ; 53 scanf("%d", &k) ; 54 while(k--) 55 { 56 scanf("%d%d%d%d",&a,&b,&c,&t) ; 57 for(int i=0; i<a; i++) 58 for(int j=0; j<b; j++) 59 for(int k=0; k<c; k++) 60 { 61 scanf("%d",&map[i][j][k]) ; 62 curtime[i][j][k] = INF ; 63 } 64 start.x = start.y = start.z = start.time = 0 ; 65 curtime[0][0][0] = 0 ; 66 int mintime = bfs(start) ; 67 if(mintime<t) 68 printf("%d\n",mintime) ; 69 else 70 printf("-1\n") ; 71 } 72 return 0 ; 73 }