题意：
有一个最多9*9个点的迷宫， 给定起点坐标（r0,c0）和终点坐标（rf,cf）， 求出最短路径并输出。
分析：
因为多了朝向这个元素， 所以我们bfs的队列元素就是一个三元组（r,c,dir），然后做好输入处理的细节， 这题的关键在于bfs中的路径还原。
其实bfs的过程就是一棵树，如下图
除了起点外， 每个点都有且只有一个父亲节点， 那么我们只需要开一个pre数组来记录每个点的父亲， 找到终点后从终点往上不断找父亲节点， 直到找到父亲节点， 那么就完成了路径还原的
步骤。
1 #include <bits/stdc++.h> 2 using namespace std; 3 struct Node{ 4 int r,c,dir; 5 Node(int r=0, int c=0, int dir=0):r(r),c(c),dir(dir) {} 6 }; 7 8 int have_edge[10][10][4][3]; 9 int d[10][10][4]; 10 Node pre[10][10][4]; 11 int r0,c0,r1,c1,rf,cf,init_dir; 12 const char* dirs = "NESW"; // 0123 13 const char* turns = "FLR";//0不动 1左 顺时针 2右 逆时针 14 15 int id_dir(char s){ return strchr(dirs,s) - dirs;} 16 int id_turn(char s){return strchr(turns,s) - turns;} 17 18 const int dr[] = {-1, 0, 1, 0}; //dirs为上右下左 19 const int dc[] = {0, 1, 0, -1}; 20 21 bool input(){ 22 char s1[99], s2[99]; 23 int o; 24 if((o = scanf("%s%d%d%s%d%d",s1,&r0,&c0,s2,&rf,&cf) )!= 6) { return false;} 25 printf("%s\n", s1); 26 init_dir = id_dir(s2[0]); 27 r1 = r0 + dr[init_dir]; 28 c1 = c0 + dc[init_dir]; 29 // printf("%d %d %d\n", init_dir,r1,c1); 30 memset(have_edge,0,sizeof(have_edge)); 31 for(;;){ 32 int r,c; 33 scanf("%d", &r); 34 if(r == 0) break; 35 scanf("%d", &c); 36 while(scanf("%s", &s2) && s2[0] != '*'){ 37 int len = strlen(s2); 38 for(int i = 1; i < len; i++){ 39 have_edge[r][c][id_dir(s2[0])][id_turn(s2[i])] = 1; 40 } 41 } 42 } 43 return true; 44 } 45 Node walk(const Node& u, int turn){ 46 int dir = u.dir; 47 if(turn == 1) dir = (u.dir+3)%4; 48 else if(turn == 2) dir = (u.dir+1) %4; 49 return Node(u.r + dr[dir], u.c + dc[dir] , dir); 50 } 51 52 bool inside(int r, int c) { 53 return r >= 1 && r <= 9 && c >= 1 && c <= 9; 54 } 55 void print_ans(Node u){ 56 vector<Node> ans; 57 for(;;){ 58 ans.push_back(u); 59 if(d[u.r][u.c][u.dir] == 0) 60 break; 61 u = pre[u.r][u.c][u.dir]; 62 } 63 ans.push_back(Node(r0,c0,init_dir)); 64 65 int cnt = 0; 66 for(int i = ans.size() -1; i >= 0; i--){ 67 if(cnt % 10 == 0) printf(" "); 68 printf(" (%d,%d)", ans[i].r, ans[i].c); 69 if(++cnt % 10 == 0) printf("\n"); 70 } 71 if(ans.size() % 10 != 0) printf("\n"); 72 } 73 void solve(){ 74 queue<Node> q; 75 memset(d,-1,sizeof(d)); 76 d[r1][c1][init_dir] = 0; 77 Node u(r1,c1,init_dir); 78 q.push(u); 79 while(!q.empty()){ 80 Node u = q.front(); q.pop(); 81 // printf("$ u %d %d %d\n",u.r, u.c,u.dir); 82 if(u.r == rf && u.c == cf){ 83 print_ans(u); 84 return; 85 } 86 for(int i = 0; i < 3; i++){ 87 Node v; 88 if(have_edge[u.r][u.c][u.dir][i]) 89 v = walk(u,i); 90 // printf("& v %d %d %d\n",v.r, v.c, v.dir); 91 if(inside(v.r,v.c) && d[v.r][v.c][v.dir] < 0){ 92 d[v.r][v.c][v.dir] = d[u.r][u.c][u.dir] + 1; 93 pre[v.r][v.c][v.dir] = u; 94 q.push(v); 95 } 96 } 97 } 98 printf(" No Solution Possible\n"); 99 } 100 int main(){ 101 while(input()){ 102 solve(); 103 } 104 return 0; 105 }
