Uva oj 816 Abbott Revenge（BFS最短路）

• 原题链接：Here！
  
  
• 闲话：看到题目的时候还是很懵的，这个迷宫很特殊，特殊的地方在对于每一个点都多出来一些要求，比如进入一个交叉点的"朝向"( NESW，北东南西 )是不同的，对应不同的"朝向"，出去的方向也是不尽相同的。好吧，根本没有思路，真不愧是Final的题。

• 部分变量设置：
  1. (r,c) 代表点的坐标，特殊的(r0,c0)代表Enterance，(r2,c2)代表Goal，(r1,c1)代表起始点
  2. dir   代表朝向，朝向有4个“N，E，S，W”，顺时针
  3. turn  代表转向方向，F直走，L左转，R右转
  4. d[r][c][dir] 代表起始点到点(r,c,dir)的最短长度
  5. p[r][c][dir] 代表点(r,c,dir)在BFS树上的父点
  6. has_edge[r][c][dir][turn] 判断是否可以转向
  7. dr[],dc[],struct Node{}的解释都在下面
  
  
• 分析：现在回过头来看它与普通迷宫题在本质上是一样的，只不过是多出了一些条件。因为现在对于每一个点都会有三个状态，行r，列c，以及进入的方向dir，所以使用三元数组(r,c,dir)来表示状态“位于点(r,c)，朝向dir”。需要注意的是起点并不是(r0,c0)，题目中描述的是在规定的入口方向进入，所以开始的点应该是(r1,c1)，d[r][c][dir] 代表起始点到点(r,c,dir)的最短长度，p[r][c][dir] 代表点(r,c,dir)在BFS树上的父点。对于任意一个状态 U(r,c,dir) 和 其后继状态 V(r',c',dir')，如果在能够转向( has_edge[r][c][dir][turn]==1 )，后继点V(r,c)在图里且还没被遍历过，就将后继状态V加入到vector中，然后更新状态V最短长度和V的父结点。如果在BFS扩增中能够到达Goal，跳出循环返回ture，如果循环结束还没有找到Goal，返回false。
  
  
• 实现：
  
  1.输入部分
  将4个方向N E S W 和 3个转向F L R 转换成数字0~3和0~2，这样可以简化问题。这技巧真很强，厉害。
  

  const char* dirs = "NESW";
  // 顺时针旋转
  const char* turns = "FLR";
  // 转弯方式 F直走，L左转，R右转
  const int dr[] = {-1, 0, 1,
  0};// 将4个方向和3种"转弯方式"编号为0~3和0~2	转弯方式：直走，左转，右转
  const int dc[] = { 0, 1, 0, -1}; 

  //
  转换函数,将字符转换成数字
  int dir_id(char c) {	return strchr(dirs,c)-dirs; }
  // 用法独特真的很强
  int turn_id(char c){
  return strchr(turns,c)-turns; }

  技巧balabala:先用字符指针指向了一个字符串常量，然后strchr(dirs,c)会返回字符c在字符串中第一次出现位置的指针，然后用 返回值 — 指向字符串的指针，就能得到字符c在字符串dirs中的"位置"了。厉害word刘。
   
  

  bool read_case(){
  char s[99],s2[99];
  scanf("%s",s);
  if(s[0]=='E')	return false;
  if(scanf("%d%d%s%d%d",&r0,&c0,s2,&r2,&c2)!=5) return false;	// 录入起点和终点信息
  printf("%sn",s);
  dir=dir_id(s2[0]);
  r1=r0+dr[dir];
  c1=c0+dc[dir];
  //除了1、2行特殊处理之外
  //对于其他行，首先输入(r,c)然后输入一些指令，指令个数和长度不确定
  memset(has_edge,0,sizeof(has_edge));
  while(1){
  int r,c;
  scanf("%d",&r);
  if(r==0)	break;
  scanf("%d",&c);
  // 指令以*结束，指令第一个字符代表朝向，其他字符代表可转向的方向
  while(scanf("%s",s)==1 && s[0]!='*'){
  for(int i=1;i<strlen(s);i++)
  has_edge[r][c][dir_id(s[0])][turn_id(s[i])]=1;
  }
  }
  return true;
  }

  
  2.输出部分

  void print_ans(Node u){
  //倒序存放到vector中
  vector<Node> nodes;
  while(1){
  nodes.push_back(u);
  if(d[u.r][u.c][u.dir]==0)	break;
  u=p[u.r][u.c][u.dir];
  }
  nodes.push_back(Node(r0,c0,dir));
  // 每行10个，注意每行开头有两个空格
  int cnt=0;
  for(int i=nodes.size()-1;i>=0;i--){
  if(cnt%10==0)	printf(" ");
  printf(" (%d,%d)",nodes[i].r,nodes[i].c);
  if(++cnt%10==0)	printf("n");
  }
  if(nodes.size()%10!=0)	printf("n");
  }

  
  3.最重要的部分
  对于任意一个状态 U(r,c,dir) 和 其后继状态 V(r',c',dir')，如果在能够转向( has_edge[r][c][dir][turn]==1 )，后继点V(r,c)在图里且还没被遍历过，就将后继状态V加入到vector中，然后更新状态V最短长度和V的父结点。如果在BFS扩增中能够到达Goal，跳出循环返回ture，如果循环结束还没有找到Goal，返回false。
  
  在分析里有一个很关键的问题，如果找到后继状态？
  

  // 接下来是"行走"函数，根据当前的状态和转弯方式，计算出后继状态
  Node walk(const Node& u,int turn){
  int dir = u.dir;
  if(turn==1)	dir=(dir + 3) % 4;	// 左转，逆时针-1，但是不能出现负数，所以+3 %4
  if(turn==2)	dir=(dir + 1) % 4;	// 右转，顺时针+1
  return Node(u.r+dr[dir],u.c+dc[dir],dir);	// 返回后继状态
  }

  
  判断点V在图里
  

  bool inside(int r,int c){
  // 判断是否在Maze里面
  return (r>=1 && r<MAX && c>=1 && c<MAX);
  }

  
  BFS
  

  void BFS(){
  queue<Node>	q;
  memset(d,-1,sizeof(d));
  Node u(r1,c1,dir);
  d[u.r][u.c][u.dir]=0;
  // 第一个点在BFS树上的父亲自然是 0
  q.push(u);
  while(!q.empty()){
  Node u=q.front();	q.pop();
  if(u.r==r2 && u.c==c2){ print_ans(u); return; }
  for(int i=0;i<3;i++){	// 四个方向进行遍历
  Node v=walk(u,i);	// v代表u向方向i走的一个后继节点
  if(has_edge[u.r][u.c][u.dir][i] && inside(v.r,v.c) && d[v.r][v.c][v.dir]<0){
  d[v.r][v.c][v.dir]=d[u.r][u.c][u.dir]+1;
  p[v.r][v.c][v.dir]=u;
  q.push(v);
  }
  }
  }
  printf("
  No Solution Possiblen");
  }

  
  
• CODE
  

  #include<vector>
  #include<queue>
  #include<cstdio>
  #include<cstring>
  using namespace std;
  const int MAX = 10;
  const char* dirs = "NESW";
  // 顺时针旋转
  const char* turns = "FLR";
  // 转弯方式 F直走，L左转，R右转
  const int dr[] = {-1, 0, 1,
  0};// 将4个方向和3种"转弯方式"编号为0~3和0~2	转弯方式：直走，左转，右转
  const int dc[] = { 0, 1, 0, -1};
  struct Node{
  int dir,r,c;
  Node(int r=0, int c=0, int dir=0):r(r),c(c),dir(dir) {}	//构造函数
  };
  int r0,c0,dir,r1,c1,r2,c2;
  // r0,c0 起点坐标 r2,c2 终点坐标
  int has_edge[MAX][MAX][4][3];	// has_edge[r][c][dir][turn],四元数组，记录点(r,c)的朝向 和 可以选择的方向
  int d[MAX][MAX][4];
  Node p[MAX][MAX][4];
  //
  转换函数,将字符转换成数字
  int dir_id(char c) {	return strchr(dirs,c)-dirs; }
  // 用法独特真的很强
  int turn_id(char c){
  return strchr(turns,c)-turns; }
  // 输入部分
  bool read_case(){
  char s[99],s2[99];
  scanf("%s",s);
  if(s[0]=='E')	return false;
  if(scanf("%d%d%s%d%d",&r0,&c0,s2,&r2,&c2)!=5) return false;	// 录入起点和终点信息
  printf("%sn",s);
  dir=dir_id(s2[0]);
  r1=r0+dr[dir];
  c1=c0+dc[dir];
  //除了1、2行特殊处理之外
  //对于其他行，首先输入(r,c)然后输入一些指令，指令个数和长度不确定
  memset(has_edge,0,sizeof(has_edge));
  while(1){
  int r,c;
  scanf("%d",&r);
  if(r==0)	break;
  scanf("%d",&c);
  // 指令以*结束，指令第一个字符代表朝向，其他字符代表可转向的方向
  while(scanf("%s",s)==1 && s[0]!='*'){
  for(int i=1;i<strlen(s);i++)
  has_edge[r][c][dir_id(s[0])][turn_id(s[i])]=1;
  }
  }
  return true;
  }
  // 接下来是"行走"函数，根据当前的状态和转弯方式，计算出后继状态
  Node walk(const Node& u,int turn){
  int dir = u.dir;
  if(turn==1)	dir=(dir + 3) % 4;	// 左转，逆时针-1，但是不能出现负数，所以+3 %4
  if(turn==2)	dir=(dir + 1) % 4;	// 右转，顺时针+1
  return Node(u.r+dr[dir],u.c+dc[dir],dir);	// 返回后继状态
  }
  bool inside(int r,int c){
  // 判断是否在Maze里面
  return (r>=1 && r<MAX && c>=1 && c<MAX);
  }
  void print_ans(Node u){
  //倒序存放到vector中
  vector<Node> nodes;
  while(1){
  nodes.push_back(u);
  if(d[u.r][u.c][u.dir]==0)	break;
  u=p[u.r][u.c][u.dir];
  }
  nodes.push_back(Node(r0,c0,dir));
  // 打印解，每行10个,
  int cnt=0;
  for(int i=nodes.size()-1;i>=0;i--){
  if(cnt%10==0)	printf(" ");
  printf(" (%d,%d)",nodes[i].r,nodes[i].c);
  if(++cnt%10==0)	printf("n");
  }
  if(nodes.size()%10!=0)	printf("n");
  }
  void BFS(){
  queue<Node>	q;
  memset(d,-1,sizeof(d));
  Node u(r1,c1,dir);
  d[u.r][u.c][u.dir]=0;
  // 第一个点在BFS树上的父亲自然是 0
  q.push(u);
  while(!q.empty()){
  Node u=q.front();	q.pop();
  if(u.r==r2 && u.c==c2){ print_ans(u); return; }
  for(int i=0;i<3;i++){	// 四个方向进行遍历
  Node v=walk(u,i);	// v代表u向方向i走的一个后继节点
  if(has_edge[u.r][u.c][u.dir][i] && inside(v.r,v.c) && d[v.r][v.c][v.dir]<0){
  d[v.r][v.c][v.dir]=d[u.r][u.c][u.dir]+1;
  p[v.r][v.c][v.dir]=u;
  q.push(v);
  }
  }
  }
  printf("
  No Solution Possiblen");
  }
  int main(){
  while(read_case()){
  BFS();
  }
  return 0;
  }

  
  
• 收获最大的是如果在遇到相同问题，明白"结点"包含哪些内容是很重要的。可以用多元数组描述一个多个参数的状态，在用数字代替字符"NESW"时也很精彩，walk()函数中找后继状态也很精彩。
  
  
• Think：优秀的代码里透露出一种美，简直不可名状，恰好听到Unbelievable--Owl City/Hanson，Oh~我突然找到了发现新奇小玩具的那种快乐~~~  Unbelievable,You haven’t seen nothing yet,I'm so amazed, those were the days.
  
  
  
  
  

最后

以上就是从容芝麻为你收集整理的Uva oj 816 Abbott Revenge（BFS最短路）的全部内容，希望文章能够帮你解决Uva oj 816 Abbott Revenge（BFS最短路）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。