UVA816Abbott’s Revenge?（BFS求最短路）

                                                                             Abbott’s Revenge?

The 1999 World Finals Contest included a problem based on a “dice maze.” At the time the problem was written, the judges were unable to discover the original source of the dice maze concept. Shortly after the contest, however, Mr. Robert Abbott, the creator of numerous mazes and an author on the subject, contacted the contest judges and identified himself as the originator of dice mazes. We regret that we did not credit Mr. Abbott for his original concept in last year’s problem statement. But we are happy to report that Mr. Abbott has offered his expertise to this year’s contest with his original and unpublished “walk-through arrow mazes.”
As are most mazes, a walk-through arrow maze is traversed by moving from intersection to intersection until the goal intersection is reached. As each intersection is approached from a given direction, a sign near the entry to the intersection indicates in which directions the intersection can be exited. These directions are always left, forward or right, or any combination of these.
Figure 1 illustrates a walk-through arrow maze. The intersections are identified as “(row, column)” pairs, with the upper left being (1,1). The “Entrance” intersection for Figure 1 is (3,1), and the “Goal” intersection is (3,3). You begin the maze by moving north from (3,1). As you walk from (3,1) to (2,1), the sign at (2,1) indicates that as you approach (2,1) from the south (traveling north) you may continue to go only forward. Continuing forward takes you toward (1,1). The sign at (1,1) as you approach from the south indicates that you may exit (1,1) only by making a right. This turns you to the east now walking from (1,1) toward (1,2). So far there have been no choices to be made. This is also the case as you continue to move from (1,2) to (2,2) to (2,3) to (1,3). Now, however, as you move west from (1,3) toward (1,2), you have the option of continuing straight or turning left. Continuing straight would take you on toward (1,1), while turning left would take you south to (2,2). The actual (unique) solution to this maze is the following sequence of intersections: (3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (1,3) (1,2) (1,1) (2,1) (2,2) (1,2) (1,3) (2,3) (3,3).
You must write a program to solve valid walk-through arrow mazes. Solving a maze means (if possible) finding a route through the maze that leaves the Entrance in the prescribed direction, and ends in the Goal. This route should not be longer than necessary, of course. But if there are several solutions which are equally long, you can chose any of them.
Input?
The input file will consist of one or more arrow mazes. The first line of each maze description contains the name of the maze, which is an alphanumeric string of no more than 20 characters. The next line contains, in the following order, the starting row, the starting column, the starting direction, the goal row, and finally the goal column. All are delimited by a single space. The maximum dimensions of a maze for this problem are 9 by 9, so all row and column numbers are single digits from 1 to 9. The starting direction is one of the characters N, S, E or W, indicating north, south, east and west, respectively.
All remaining input lines for a maze have this format: two integers, one or more groups of characters, and a sentinel asterisk, again all delimited by a single space. The integers represent the row and column, respectively, of a maze intersection. Each character group represents a sign at that intersection. The first character in the group is N, S, E or W to indicate in what direction of travel the sign would be seen. For example, S indicates that this is the sign that is seen when travelling south. (This is the sign posted at the north entrance to the intersection.) Following this first direction character are one to three arrow characters. These can be L, F or R indicating left, forward, and right, respectively.
The list of intersections is concluded by a line containing a single zero in the first column. The next line of the input starts the next maze, and so on. The end of input is the word END on a single line by itself.
Output?
For each maze, the output file should contain a line with the name of the maze, followed by one or more lines with either a solution to the maze or the phrase “No Solution Possible”. Maze names should start in column 1, and all other lines should start in column 3, i.e., indented two spaces. Solutions should be output as a list of intersections in the format “(R,C)” in the order they are visited from the start to the goal, should be delimited by a single space, and all but the last line of the solution should contain exactly 10 intersections.
The first maze in the following sample input is the maze in Figure 1.
Sample Input
Output for the Sample Input
SAMPLE 3 1 N
3 3
1 1 WL NR *
1 2 WLF NR ER *
1 3 NL ER *
2 1 SL WR NF *
2 2 SL WF ELF *
2 3 SFR EL *
0
NOSOLUTION 3 1 N
3 2
1 1 WL NR *
1 2 NL ER *
2 1 SL WR NFR *
2 2 SR EL *
0
END
SAMPLE 
(3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (1,3) (1,2) (1,1) (2,1)
(2,2) (1,2) (1,3) (2,3) (3,3)
NOSOLUTION?
No Solution Possible

分析

题目很长， 意思很难懂是吧！ 有“紫书”的请参考 165 页。 作者说这个题非常的重要，一定要弄懂。 然而我弄懂题意都费了老大的劲！！！ （哎！蒟蒻是何等的悲哀！）。
简述一下题意吧：
        有一个 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][dir]表示初始状态到（r， c， dir）的最短路长度， 并且用 p[r][dir]保存了状态（r， c， dir）在BFS树中的父结点。

规律（==心得）：
很多复杂的迷宫问题都可以转化成最短路问题， 然后用BFS求解。 在套用BFS框架之前， 需要先搞清楚图中的“结点”包含哪些内容。

代码实现详细思路：
第一步是读入点的坐标和对该点的描述， 并处理该点， 用has_edge[r][dir][turn]来记录下一步可以往哪走。
第二步把第一个结点放入队列， 搜索周围各个方向， 并把可走的结点放入队列（同时该结点出队）即BFS。并用d[r][dir]记录下来长度， 用p[r][dir]记录下来父结点
第三步搜到目的结点时，结束搜索。
第四步从目的点追溯，到起点， 再把路径输出！

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
struct Node {
  int r, c, dir; // 位于(r,c)朝向dir(0~3表示四个方向N, E, S, W)
  Node(int r=0, int c=0, int dir=0):r(r),c(c),dir(dir) {}
};
const int maxn = 10;
const char* dirs = "NESW"; // 顺时针旋转。 
const char* turns = "FLR";//“三种转弯方式”。 
int has_edge[maxn][maxn][4][3];// 表示当前状态（r，c，dir），是否可以沿着转弯方向[trun]行走。 
int d[maxn][maxn][4];          //表示初始状态到（r，c，dir）的最短路长度。 
Node p[maxn][maxn][4];          //同时用p[r][dir]保存了状态(r, c, dir)在BFS树中的父结点。 
int r0, c0, dir, r1, c1, r2, c2;
//把四个方向和3种“转弯方式”编号0~3和0~2. 
int dir_id(char c) { return strchr(dirs, c) - dirs; }
int turn_id(char c) { return strchr(turns, c) - turns; }
//用于转弯。 
const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, 1, 0, -1};
Node walk(const Node& u, int turn) { 
  int dir = u.dir;                    //直行， 方向不变 
  if(turn == 1) dir = (dir + 3) % 4; // 逆时针 ，转向 
  if(turn == 2) dir = (dir + 1) % 4; // 顺时针 ，转向 
  return Node(u.r + dr[dir], u.c + dc[dir], dir);//下一步可能的状态 
}
//判断是否出界 
bool inside(int r, int c) {
  return r >= 1 && r <= 9 && c >= 1 && c <= 9;
}
//读取r0，c0，dir，并计算出r1，c1， 然后读入has_edge数组。 
bool read_case() {
  char s[99], s2[99];
  if(scanf("%s%d%d%s%d%d", s, &r0, &c0, s2, &r2, &c2) != 6) return false;
  printf("%sn", s);
  dir = dir_id(s2[0]);
  r1 = r0 + dr[dir];
  c1 = c0 + dc[dir];
  memset(has_edge, 0, sizeof(has_edge));
  for(;;) {
    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][dir_id(s[0])][turn_id(s[i])] = 1;
    }
  }
  return true;
}
void print_ans(Node u) {
  // 从目标结点逆序追溯到初始结点。 
  vector<Node> nodes;
  for(;;) {
    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");
}
//BFS主过程。 
void solve() {
  queue<Node> q;
  memset(d, -1, sizeof(d));
  Node u(r1, c1, dir);
  d[u.r][u.c][u.dir] = 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);      //下一步的状态 
      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;//最短长度加 1. 
        p[v.r][v.c][v.dir] = u;//记录父结点。 
        q.push(v);  
      }
    }
  }
  printf("  No Solution Possiblen");//走了所有可以走的可能， 无法到达终点。 
}
int main() {
  while(read_case()) {
    solve();
  }
  return 0;
}