首页 > 代码库 > HDU 1253 三维数组的图上找最短路

HDU 1253 三维数组的图上找最短路

题目大意:

从三维空间的(0,0,0)出发到(a-1,b-1,c-1),每移动一个都要时间加一,计算最短时间

 

根据六个方向,开个bfs,像spfa那样计算最短路径就行了,但是要1200多ms,也不知道有没有更好的方法

 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <queue> 5 using namespace std; 6 int dp[52][52][52] , a , b , c; 7 bool wall[52][52][52] , vis[52][52][52]; 8 int dir[6][3] = {{0,0,1} , {0,1,0} , {1,0,0} , {0,0,-1} , {0,-1,0} , {-1,0,0}}; 9 struct Node{10     int x , y , z;11     Node(int x = 0 , int y = 0 , int z = 0):x(x),y(y),z(z){}12 };13 queue<Node> q;14 15 bool ok(int x , int y , int z)16 {17     if(x<0 || x>=a) return false;18     if(y<0 || y>=b) return false;19     if(z<0 || z>=c) return false;20     if(wall[x][y][z]) return false;21     return true;22 }23 24 int main()25 {26   //  freopen("a.in" , "r" , stdin);27     int T , t , w;28     scanf("%d" , &T);29     while(T--){30         scanf("%d%d%d%d" , &a , &b , &c , &t);31         for(int i = 0 ; i<a ; i++)32             for(int j = 0 ; j<b ; j++)33                 for(int k = 0 ; k<c ; k++){34                     scanf("%d" , &w);35                     if(w) wall[i][j][k] = true;36                     else wall[i][j][k] = false;37                 }38         memset(dp , 0x3f , sizeof(dp));39         memset(vis , 0 , sizeof(vis));40         dp[0][0][0] = 0;41         q.push(Node(0,0,0));42         while(!q.empty()){43             Node u = q.front();44             q.pop();45             vis[u.x][u.y][u.z] = false;46             for(int i = 0 ; i<6 ; i++){47                 Node v;48                 v.x = u.x+dir[i][0];49                 v.y = u.y+dir[i][1];50                 v.z = u.z+dir[i][2];51                 if(ok(v.x,v.y,v.z)){52                     if(dp[v.x][v.y][v.z] > dp[u.x][u.y][u.z] + 1){53                         dp[v.x][v.y][v.z] = dp[u.x][u.y][u.z] + 1;54                         if(!vis[v.x][v.y][v.z]){55                             q.push(v);56                             vis[v.x][v.y][v.z] = true;57                         }58                     }59                 }60             }61         }62 63         if(dp[a-1][b-1][c-1] > t) puts("-1");64         else printf("%d\n" , dp[a-1][b-1][c-1]);65     }66     return 0;67 }

 

HDU 1253 三维数组的图上找最短路