Abbott's Revenge UVA 816（图 BFS）

缺乏、安全感 2024-02-17 18:53 19阅读 0赞

题目大意：

有一个 9 \* 9 的交叉点的迷宫。 输入起点， 离开起点时的朝向和终点， 求最短路（多解时任意一个输出即可）。进入一个交叉点的方向（用NEWS表示不同方向）不同时， 允许出去的方向也不相同。 例如：1 2 WLF NR ER \* 表示如果 进去时朝W（左）， 可以 左转（L）或直行（F）， 如果 朝N只能右转（R） 如果朝E也只能右转。\* 表示这个点的描述结束啦！

输入有： 起点的坐标， 朝向， 终点的坐标。然后是各个坐标，和各个坐标点的情况（进去方向和可以出去的方向） 以\*号表示各个坐标点描述的结束。

本题和普通的迷宫在本质上是一样的， 但是由于“朝向”也起了关键的作用， 所以需要一个三元组（r，c, dir）表示位于（r， c）面朝dir 的状态。 假设入口位置为（r0，c0）朝向为dir ， 则初始状态并不是（r0， c0， dir）， 而是（r1， c1， dir）因为开始时他别无选择， 只有一个规定的方向。 其中， （r1， c1）是沿着方向dir走一步之后的坐标， dir刚好是他进入该点时的朝向。 此处用d\[r\]\[c\]\[dir\]表示初始状态到（r， c， dir）的最短路长度， 并且用 p\[r\]\[c\]\[dir\]保存了状态（r， c， dir）在BFS树中的父结点

输入：第一行输入迷宫的名字，第二行迷宫的初始位置、方向以及终点位置，接下来每行输入迷宫中 每个点的状态（进入时方向+在该方向下该转向那些方向）；以0结束一组数据。

1.  \#include<cstdio>
2.  \#include<queue>
3.  \#include<vector>
4.  \#include<cstring>
5.  using namespace std;
6.  const int maxn=10;
7.  struct note\{ 
8.   int r,c,dir;
9.   note(int r1=0,int c1=0,int dir1=0):r(r1),c(c1),dir(dir1)\{\}
10.  \};
11. const char \* dirs="NESW"; //顺时针旋转 
12. const char \* turns="FLR"; //旋转方向 
13. int turn\_id(char ch)\{return strchr(turns,ch)-turns;\}
14. int dir\_id(char ch)\{return strchr(dirs,ch)-dirs;\}
15.   
    
16. int has\_edge\[maxn\]\[maxn\]\[4\]\[3\]; //当前状态（r,c,dir）是否可以沿着转弯方向走（turn）
17. int d\[maxn\]\[maxn\]\[4\]; //初始状态到(r,c,dir)的最短路径 
18. note path\[maxn\]\[maxn\]\[4\]; //保存路径 
19. int r0,c0,dir,r1,c1,r2,c2; //(r0,c0,dir0)初始状态，（r2,c2）最终状态 
20. const int dr\[\]\[2\]=\{ \{-1,0\},\{0,1\},\{1,0\},\{0,-1\}\}; //向NESW（顺时针）方向移动时的坐标变化
21. bool read()\{ 
22.  char s\[20\];scanf("%s",s);
23.  if(!strcmp(s,"END"))return false;
24.  printf("%s\\n",s);
25.  scanf("%d%d%s%d%d",&r0,&c0,s,&r2,&c2);
26. //假设入口位置为(r0,c0),方向为dir，则初始状态并不是（r0,c0,dir），而是(r1,c1,dir)，其中(r1,c1)是(r0,c0)沿着dir走一步之后的坐标（理解这一点很重要）
27.  dir=dir\_id(s\[0\]);
28.  r1=r0+dr\[dir\]\[0\];
29.  c1=c0+dr\[dir\]\[1\];
30.   
    
31.  memset(has\_edge,0,sizeof(has\_edge));
32.  while(true)\{ 
33.  int r,c;
34.  char s1\[5\];
35.  scanf("%d",&r);
36.  if(r==0)break;
37.  scanf("%d",&c);
38.  while(scanf("%s",s1)==1 && s1\[0\]!='\*')\{ 
39.  for(int i=1;i<strlen(s1);i++)
40.  has\_edge\[r\]\[c\]\[dir\_id(s1\[0\])\]\[turn\_id(s1\[i\])\]=1;
41.  \}
42.  \}
43.  return true;
44. \}
45.   
    
46. void print(note u)\{ 
47.  vector<note>vec;
48.  while(true)\{ 
49.  vec.push\_back(u);
50.  if(d\[u.r\]\[u.c\]\[u.dir\]==1)break;
51.  u=path\[u.r\]\[u.c\]\[u.dir\];
52.  \}
53. vec.push\_back(note(r0,c0,dir));
54.  int count=0;
55.  for(int i=vec.size()-1;i>=0;i--)\{ 
56.  if(count%10==0&& count )printf("\\n");
57.  if(count%10==0 )printf(" (%d,%d)",vec\[i\].r,vec\[i\].c);
58.  else printf(" (%d,%d)",vec\[i\].r,vec\[i\].c);
59.  count++;
60.  \}
61.  printf("\\n");
62. \}
63.   
    
64. note walk(const note &u,int turn)\{ 
65.  int dir=u.dir;
66.  if(turn == 1)dir=(dir+3)%4; //逆时针 
67.  if(turn == 2)dir=(dir+1)%4; //顺时针 
68.  return note(u.r+dr\[dir\]\[0\],u.c+dr\[dir\]\[1\],dir);
69. \}
70. //接下来就是BFS的框架了
71. void solve()\{ 
72.  queue<note>q;
73.  memset(d,0,sizeof(d));
74.  q.push(note(r1,c1,dir));
75.  d\[r1\]\[c1\]\[dir\]=1;
76.  while(!q.empty())\{ 
77.  note u=q.front();q.pop();
78.  if(u.r==r2 && u.c== c2)\{ 
79.  print(u);
80.  return ;
81.  \}
82.  for(int i=0;i<3;i++)\{ 
83.  note v=walk(u,i);
84.  if(has\_edge\[u.r\]\[u.c\]\[u.dir\]\[i\] && d\[v.r\]\[v.c\]\[v.dir\]==0)\{ 
85.  d\[v.r\]\[v.c\]\[v.dir\]=d\[u.r\]\[u.c\]\[u.dir\]+1;
86.  path\[v.r\]\[v.c\]\[v.dir\]=u;
87.  q.push(v);
88.  \}
89.  \}
90.  \}
91.  printf(" No Solution Possible\\n");
92. \}
93. int main()\{ 
94.  while(read())\{ 
95.  solve();
96.  \} 
97.  return 0;
98. \}