思路分析：
本题属于求最短路的问题，用图的BFS即可解决。难点在于如何处理各个结点处的位置。
设置一个三元组(r, c, dir)来表示“位于r，c 面朝dir”这一状态，其中r c为位置，dir为朝向，d[r][c][dir]来表示从初始状态到(r, c, dir)状态的最短路长度。假设入口位置为(r0,c0)，本题初始状态应是(r1,c1,dir)，即从入口往前走了一步的位置。（即初始时候已经从入口点出发了）
用一个四元组g[r][c][dir][turn]来表示道路情况,即在r，c位置，朝向dir时候向turn方向转。值为1表示这一路径存在，否则表示不存在。
注意点：
1.为了处理便捷，将面朝方向以及转向转化为整数表示。
2.左右转的处理，利用取余运算
3.用pre数组来保存最短路上点v的前一节点u，最后倒推并插入一个vector容器，然后倒序输出即可
题解：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int MAX = 10;
const char* dirs = "NESW";//北东南西 顺时针方向
const char* turns = "FLR";//直走，左转，右转
const int addr[4] = {-1, 0, 1, 0};
const int addc[4] = {0, 1, 0, -1}; struct Node{int r, c, dir;Node(int a, int b, int e){r = a, c = b, dir = e;}Node(){}
};
int r0, c0, r1, c1, re, ce, dir;//起始坐标r0 c0 按起始坐标和方向获得的第一个位置 目的坐标 re ce 方向dir
int g[MAX][MAX][4][3], d[MAX][MAX][4];//表示x，y处可否能在各中方向进入后进行各种转向
Node pre[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_input(){char s[100];scanf("%s", s);if(strcmp(s,"END") == 0) return false;printf("%s\n", s);scanf("%d %d %c %d %d", &r0, &c0, s, &re, &ce);dir = dir_id(s[0]);r1 = r0 + addr[dir];c1 = c0 + addc[dir];fill(g[0][0][0], g[0][0][0]+MAX*MAX*4*3, 0);while(1){int r,c;scanf("%d", &r);if(r == 0) break;scanf("%d", &c);while(scanf("%s", s) && s[0] != '*'){int len = strlen(s);for(int i = 1; i < len; i++){g[r][c][dir_id(s[0])][turn_id(s[i])] = 1;}}}return true;
}bool inside(int r, int c){return r >= 1 && r <= 9 && c >= 1 && c <= 9;
}Node walk(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+addr[dir], u.c+addc[dir], dir);
}void print(Node u){vector<Node> nodes;while(1){nodes.push_back(u);if(d[u.r][u.c][u.dir] == 0) break;u = pre[u.r][u.c][u.dir];}nodes.push_back(Node(r0,c0,dir));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 solve(){queue<Node> q;fill(d[0][0], d[0][0]+MAX*MAX*4, -1);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 == re && u.c == ce){ print(u); return;}for(int i = 0; i < 3; i++){Node v = walk(u, i);if(g[u.r][u.c][u.dir][i] && inside(v.r, v.c) && d[v.r][v.c][v.dir] < 0){//r c合法 且通，且未处理过 d[v.r][v.c][v.dir] = d[u.r][u.c][u.dir] + 1;pre[v.r][v.c][v.dir] = u;q.push(v);}}}printf(" No Solution Possible\n");
}int main(){while(read_input()){solve();}return 0;
}