HDU杭电 1253 胜利大逃亡（图 BFS）

冷不防 2024-02-17 18:53 5阅读 0赞

本题难度并不大，一个普通的用BFS求解的题，值得注意的是数据的输入（三维数据输入被绕了几圈）；还有就是最后的出口可以表示墙，无法出去（就是没考虑到这点WA了一次）；剩下的就是BFS的常规思路及框架了。

1.  \#include<cstdio>
2.  \#include<vector>
3.  \#include<queue>
4.  \#include<cstring>
5.  using namespace std;
6.  const int len=50+10;
7.  int K,A,B,C,T;
8.  struct node\{ 
9.   int x,y,z;
10.  node(int x1=0,int y1=0,int z1=0):x(x1),y(y1),z(z1)\{\}
11. \};
12. int d\[len\]\[len\]\[len\]; //从初始位置到当前位置的长度
13. int p\[len\]\[len\]\[len\]; //输入数据的保存
14. node n0,nt; //初始位置和最终位置
15. void read()\{ 
16.  scanf("%d%d%d%d",&A,&B,&C,&T);
17.  n0.x=0,n0.y=0,n0.z=B-1;
18.  nt.x=A-1,nt.y=C-1,nt.z=0;
19.  for(int x=0;x<A;x++)
20.  for(int z=B-1;z>=0;z--)
21.  for(int y=0;y<C;y++)
22.  scanf("%d",&p\[x\]\[y\]\[z\]);
23. \}
24. const int dir\[\]\[3\]=\{ \{0,0,1\},\{0,0,-1\},\{0,-1,0\},\{0,1,0\},\{1,0,0\},\{-1,0,0\}\}; //上下左右前后 
25. void print(const node &u)\{ 
26.  if(d\[u.x\]\[u.y\]\[u.z\]<=T)
27.  printf("%d\\n",d\[u.x\]\[u.y\]\[u.z\]);
28.  else printf("-1\\n");
29. \}
30. bool isValid(const node &v)\{ 
31.  return v.x>=0 && v.x<A && v.y>=0 && v.y<C && v.z>=0 && v.z<B;
32. \}
33. void bfs()\{ 
34.  queue<node>q;
35.  q.push(n0);
36.  memset(d,0,sizeof(d));
37.   
    
38.  while(!q.empty())\{ 
39.  node u=q.front();q.pop();
40.  if(u.x== nt.x && u.y== nt.y && u.z == nt.z)\{ 
41.  print(u);
42.  return ;
43.  \} 
44.  for(int i=0;i<6;i++)\{ 
45.  node v=node(u.x+dir\[i\]\[0\],u.y+dir\[i\]\[1\],u.z+dir\[i\]\[2\]);
46.  if(d\[v.x\]\[v.y\]\[v.z\]==0 && isValid(v) && !p\[v.x\]\[v.y\]\[v.z\])\{ //p\[\]\[\]\[\]=1时表示墙，不能放入队列中 
47.  d\[v.x\]\[v.y\]\[v.z\]=d\[u.x\]\[u.y\]\[u.z\]+1;
48.  q.push(v);
49.  \}
50.  \}
51.  \}
52.  printf("-1\\n"); //这里值得注意，出口可以表示墙，此时无法出去，通过这条语句输出结果。
53. \}
54. int main()\{ 
55.  scanf("%d",&K);
56.  while(K--)\{ 
57.  read();
58.  bfs();
59.  \}
60.  return 0;
61. \}