BFS。同时记录每个进队节点的父亲节点，以便于输出路径。

细节很多，较为复杂，请见下面的代码（含有详细注释）。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
struct Node
{
    int r,c,dir;
    Node(int r=0,int c=0,int dir=0):r(r),c(c),dir(dir) {}
}; // (r,c,dir) 表示位于 (r,c)，面朝 dir 这个状态

const int maxn=15;
const char* dirs="NESW"; // 顺时针，方便操作
const char* turns="FLR"; // 转向
/*
N:上
E:右
S:下
W:左
*/

// strchr(str,ch) 的作用是在 str 中找到第一个 ch 出现的位置并返回改位置的指针
// 这两个函数的作用是将输入中的字母转化成编号，方便存储
int dirId(char c) {return strchr(dirs,c)-dirs;}
int turnId(char c) {return strchr(turns,c)-turns;}

// dr[],dc[] 是方向数组，对应的4个方向为 上 右 下 左
const int dr[]={-1,0,1,0};
const int dc[]={0,1,0,-1};

// has_edge[r][c][dir][turn] 表示在 (r,c) 且面朝 dir 时是否可以向 turn 方向转
// d[r][c][dir] 表示从 (r1,c1) 到 (r,c) 的最短路的长度
// p[r][c][dir] 表示当前状态的上一个状态
int has_edge[maxn][maxn][4][3],d[maxn][maxn][4];
Node p[maxn][maxn][4];
int r0,c0,dir,r1,c1,r2,c2;
// 注意，起点是 (r0,c0)，但起始状态点是从起点沿着给定的方向 dir 走1步之后的位置 (r1,c1)

Node walk(const Node& u,int turn)  // 从 u 按照 turn 走
{
    int dir=u.dir;
    // turn=0 即 F，什么都不用做
    if(turn==1) dir=(dir+3)%4;  // turn=1 即 L，向左转
    if(turn==2) dir=(dir+1)%4;  // turn=2 即 R，向右转
    // 提前设计好了 dr[],dc[] 就是按照顺时针排列的，所以左转是逆时针，右转是顺时针
    return Node(u.r+dr[dir],u.c+dc[dir],dir);  // 返回走过后所处的位置
}

// 判断是否出界，题目中有说最上面的是第一行，最左边的是第一列，9×9 的格子
bool inside(int r,int c) {return r>=1&&r<=9&&c>=1&&c<=9;}

// 用于处理读入信息
bool read()
{
    char s[105],s2[105];
    if(scanf("%s%d%d%s%d%d",s,&r0,&c0,s2,&r2,&c2)!=6)return false;
    printf("%s\n",s);
    dir=dirId(s2[0]);
    r1=r0+dr[dir];
    c1=c0+dc[dir];
    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]!='*')
        {
            int len=strlen(s);
            for(int i=1;i<len;i++) has_edge[r][c][dirId(s[0])][turnId(s[i])]=1;
        }
    }
    return true;
}

// 输出答案（路径）
void print(Node u)
{
    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));
    int cnt=0;
    for(int i=(int)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((int)nodes.size()%10!=0)printf("\n");
}

// BFS 解决
void bfs()
{
    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(u);return;}
        for(int i=0;i<3;i++)  // 三种转弯方向：FLR
        {
            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;
                p[v.r][v.c][v.dir]=u;
                q.push(v);
            }
        }
    }
    printf("  No Solution Possible\n");
}

int main()
{
    while(read())bfs();
    return 0;
}