题目大意：
这个题目就是大小不超过9*9的迷宫，给你起点终点和起点的方向，让你进行移动
移动特别之处是不一定上下左右都可以，只有根据方向确定可以走的方向。
思路：
需要写一个读入函数，这个需要读入起点，终点，方向（简单），还有就是接下来几行的不同位置
可以转的方向，可以写几个函数，根据函数来判断方向，最后转换成数字，用bool类型数组0，1分别代表
可以或不可以。
之后要写一个bfs，这个比较简单，就是和普通差不多，但是之后要输出路线，所以
要有两个数组，一个用来存储路程，一个用来存储路线。
具体一点的bfs，就是先把初始位置放进去，写清楚距离，之后进去while，while里面要有一个判断
是否到了终点，之后就用walk函数进行走路，然后判断这一步是否合法，合法就走下一步，不过，走下一步之前，记住两个点
第一个就是去记录距离，第二个就是记录路线。
最后有一个输出函数，用vector
这个题目就是大小不超过9*9的迷宫，给你起点终点和起点的方向，让你进行移动
移动特别之处是不一定上下左右都可以，只有根据方向确定可以走的方向。
思路：
需要写一个读入函数，这个需要读入起点，终点，方向（简单），还有就是接下来几行的不同位置
可以转的方向，可以写几个函数，根据函数来判断方向，最后转换成数字，用bool类型数组0，1分别代表
可以或不可以。
之后要写一个bfs，这个比较简单，就是和普通差不多，但是之后要输出路线，所以
要有两个数组，一个用来存储路程，一个用来存储路线。
具体一点的bfs，就是先把初始位置放进去，写清楚距离，之后进去while，while里面要有一个判断
是否到了终点，之后就用walk函数进行走路，然后判断这一步是否合法，合法就走下一步，不过，走下一步之前，记住两个点
第一个就是去记录距离，第二个就是记录路线。
最后有一个输出函数，用vector
总的来说，这也是一个最短路问题，和robot有点像，就是每个位置不一定每个方向都是对的。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
string name;
int x1,x2,y1,y2,dir,x,y;
int dx[]={,,,-};
int dy[]={,,-,};
const char *dirs="ESWN";
const char *turns="FLR";
const int maxn=;
bool has_edge[maxn][maxn][][];
int d[maxn][maxn][]; int dir_id(char c)
{
return (strchr(dirs,c)-dirs);
}
int turn_id(char c)
{
return (strchr(turns,c)-turns);
} struct node
{
int x,y,dir;
node(int x=,int y=,int dir=):x(x),y(y),dir(dir){}
}b[maxn][maxn][]; node walk(const node& u,int turn)
{
int dir=u.dir;
if(turn==) dir=(dir+)%;
if(turn==) dir=(dir+)%;
return node(u.x+dx[dir],u.y+dy[dir],dir);
} bool scan()
{
memset(has_edge,,sizeof(has_edge));
cin>>name;
if(name=="END") return false;
char s[];
cin>>x>>y>>s>>x2>>y2; dir=dir_id(s[]);
x1=x+dx[dir];
y1=y+dy[dir];
int r,c;
while(cin>>r)
{
if(r==) break;
cin>>c;
char s1[];
while(cin>>s1)
{
if(s1[]=='*') break;
int l=strlen(s1);
for(int i=;i<l;i++)
{
has_edge[r][c][dir_id(s1[])][turn_id(s1[i])]=;
// printf("has_edge[%d][%d][%d][%d]=1;\n",r,c,dir_id(s1[0]),turn_id(s1[i]));
}
}
}
cout<<name<<endl;
return true;
} bool judge(int r, int c)
{
return r >= && r <= && c >= && c <= ;//迷宫从1开始
} void print_ans(node exa)
{
vector<node>nodes;
while(true)
{
nodes.push_back(exa);
if(d[exa.x][exa.y][exa.dir]==) break;
exa=b[exa.x][exa.y][exa.dir];
}
nodes.push_back(node(x,y,dir));
int cnt=;
for(int i=nodes.size()-;i>=;i--)
{
if(cnt%==) printf(" ");
cnt++;
printf(" (%d,%d)",nodes[i].x,nodes[i].y);
if(cnt%==) printf("\n");
}
if(cnt%!=) printf("\n");
} void bfs()
{
queue<node>que;
node exa=node(x1,y1,dir);
memset(d,-,sizeof(d));
d[exa.x][exa.y][exa.dir]=;
que.push(exa);
while(!que.empty())
{
node exa=que.front();
//printf("%d %d %d\n",exa.x,exa.y,exa.dir);
que.pop();
if(exa.x==x2&&exa.y==y2)
{
print_ans(exa);
return ;
}
for(int i=;i<;i++)
{
node v=walk(exa,i);
// printf("www %d %d %d %d\n",v.x,v.y,v.dir,i);
// printf("d[%d][%d][%d]=%d\n",v.x,v.y,v.dir,d[v.x][v.y][v.dir]);
if(has_edge[exa.x][exa.y][exa.dir][i]&&judge(v.x,v.y)&&d[v.x][v.y][v.dir]<)
{
d[v.x][v.y][v.dir]=d[exa.x][exa.y][exa.dir]+;
b[v.x][v.y][v.dir]=exa;
//printf("%d %d %d\n",v.x,v.y,v.dir);
que.push(v);
}
}
}
printf(" No Solution Possible\n");
} int main()
{
while(scan())
{ bfs();
}
return ;
}