好复杂TAT
主要是BFS
#include<iostream>
#include<vector>
#include<queue>
#include<cstdio>
#include<cstring>
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) {}
};
const int maxn = 100;
const char dirs[]={"NESW"};
const char turns[]={"FLR"};
const int dr[]={-1,0,1, 0}; //朝N,E,S,W走
const int dc[]={ 0,1,0,-1};int d[10][10][4];
Node p[10][10][4];
int islegal[10][10][4][3];
int dir_id(char c){ return strchr(dirs,c)-dirs;}
int turn_id(char c){ return strchr(turns,c)-turns;}
void read();
Node walk(const Node& u,int turn);
void solve();
bool inside(int i,int j);
void print_solution(Node u);
int r1,c1,dir; //入口的下一个点
int r2,c2; //terminal
int r0,c0;int main()
{string name;while(cin>>name){if(name=="END") break;cout<<name<<endl;read();solve();}return 0;
}
void solve()
{queue<Node> q;Node u(r1,c1,dir);memset(d,-1,sizeof(d)); d[r1][c1][dir]=0;q.push(u);while(!q.empty()){Node u=q.front();q.pop();if(u.r==r2&&u.c==c2) {print_solution(u);return;} //finishfor(int i=0;i<3;i++) //turn front,left,right;{Node v=walk(u,i); //朝上左右走;if(islegal[u.r][u.c][u.dir][i]&&inside(v.r,v.c)&&d[v.r][v.c][v.dir]<0){q.push(v);p[v.r][v.c][v.dir]=u; //标明父节点，即前一步 d[v.r][v.c][v.dir]=d[u.r][u.c][u.dir]+1; //路程+1 }}}printf(" No Solution Possible\n");
}
Node walk(const Node& u,int turn) //走前，左，右输出面朝方向
{int dir=u.dir;if(turn==1) dir = (dir+3)%4; //turn leftif(turn==2) dir = (dir+1)%4; //turn rightreturn Node(u.r+dr[dir],u.c+dc[dir],dir);
}
bool inside(int i,int j)
{if(i>9||i<1||j>9||j<1) return false;return true;
}
void print_solution(Node u)
{vector<Node> v;while(1) { v.push_back(u); if(d[u.r][u.c][u.dir] == 0) break; u = p[u.r][u.c][u.dir]; } v.push_back(Node(r0,c0,dir));int cnt=0;for(int i=v.size()-1;i>=0;i--){if(cnt%10==0) printf(" ");printf(" (%d,%d)",v[i].r,v[i].c);if(++cnt%10==0) putchar('\n');}if(v.size()%10 != 0) printf("\n");
}void read()
{scanf("%d%d",&r0,&c0);char d;scanf("%c",&d); cin>>d; //cin不读空格回车; dir=dir_id(d);r1=r0+dr[dir];c1=c0+dc[dir];scanf("%d%d",&r2,&c2);int x,y;memset(islegal,0,sizeof(islegal));while(scanf("%d",&x)==1&&x){scanf("%d",&y);string s;while(cin>>s){if(s=="*") break;int dire=dir_id(s[0]);for(int i=1;i<s.length();i++)islegal[x][y][dire][turn_id(s[i])]=1;}}}