HDU1253 胜利大逃亡【BFS】

题目链接:

?pid=1253

题目大意:

有一个三维立体的立方体迷宫,开始的位置为(0,0,0),离开的位置为(A-1,B-1,C-1),迷宫中0表示

路,1表示墙,你只能从一个坐标走到相邻的六个坐标其中的一个。问:离开这个迷宫的最短时间

是多少。

思路:

可以很容易的想到BFS找到最短的路径。只不过是三维的,,用个二维数组存放六个方向。用队列来

实现BFS。

AC代码:

#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<queue>using namespace std;const int Dire[6][3] = {{0,0,-1},{0,0,1},{0,-1,0},{0,1,0},{-1,0,0},{1,0,0}};int Map[55][55][55];struct Node{int x;int y;int z;int time;};int BFS(int A,int B,int C,int Time){Node p,p1;int ans = 0xffffff0;p.x = 0;p.y = 0;p.z = 0;p.time = 0;queue<Node> q;q.push(p);while( !q.empty() ){p = q.front();q.pop();if(p.time > Time)continue;if(p.x == A-1 && p.y == B-1 && p.z == C-1)ans = min(ans,p.time);for(int i = 0; i < 6; ++i){p1.x = p.x + Dire[i][0];p1.y = p.y + Dire[i][1];p1.z = p.z + Dire[i][2];if(p1.x < 0 || p1.y < 0 || p1.z < 0 || p1.x >= A || p1.y >= B || p1.z >= C)continue;if(Map[p1.x][p1.y][p1.z])continue;Map[p1.x][p1.y][p1.z] = 1;p1.time = p.time + 1;q.push(p1);}}return ans;}int main(){int T;scanf("%d", &T);while(T–){int A,B,C,Time;scanf("%d%d%d%d",&A,&B,&C,&Time);for(int i = 0; i < A; ++i)for(int j = 0; j < B; ++j)for(int k = 0; k < C; ++k)Map[i][j][k] = 1;for(int i = 0; i < A; ++i)for(int j = 0; j < B; ++j)for(int k = 0; k < C; ++k)scanf("%d",&Map[i][j][k]);int ans = BFS(A,B,C,Time);if(ans > Time)printf("-1\n");elseprintf("%d\n",ans);}return 0;}

即将转出来的那一面,是快乐或痛苦,是爱还是恨。

HDU1253 胜利大逃亡【BFS】

相关文章:

你感兴趣的文章:

标签云: