# UVa 816 - Abbott's Revenge

---
# 題目大意
有一個最多9*9個的迷宮。輸入起點、離開起點時的朝向和終點，每個點有限制能走的方向，輸出最短路。
要注意初始狀態是 **剛剛離開入口** ，所以即使出口和入口重合，最短路也不爲空。

---
# 題解
有夠麻煩又一堆問題的BFS。因為有朝向哪邊的問題，所以需要多記錄現在的朝向，整體來說就是多一維的BFS。然後設計一下dir陣列對應左、右、前的關係。一邊走一邊紀錄父節點，最後倒著推回去輸出路徑

---

#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#include <map>
#include <algorithm>
#define ll long long
#define pb push_back
#define pf push_front
#define ft first
#define sec second
#define pr pair<int,int>
#define ISCC ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std; 
int sx ,sy ,ex ,ey;
int dir[][2] = {{0,1},{1,0},{0,-1},{-1,0}} ,cas ,edge[15][15] ,vis[15][15][4] ,x1 ,y1 ,d[15][15][4];  
string name ,s;
char way[] = {'E','S','W','N','L','R','F'};
vector<int> g[15][15][4]; /*每個點可以往哪走 */
struct node{
	int gx ,gy;
	int from;
	node():gx(),gy(),from(){}
	node(int a ,int b ,int c):gx(a),gy(b),from(c){}
}fa[10][10][4]; /*紀錄BFS樹的父節點 */
map<char ,int> mp;
char st;
void print(node v)
{
	vector<node> ans;
	while(1) /*從終點跑回去 */
	{
		ans.pb(v); 
		if(d[v.gx][v.gy][v.from]==0) break;
		v = fa[v.gx][v.gy][v.from];
	}ans.pb(node(sx,sy,mp[st]));
	for(int i=ans.size()-1 ,cnt=1 ;i>=0 ;i-- ,cnt++) /*要倒著輸出 */
	{
		printf(" (%d,%d)",ans[i].gx ,ans[i].gy);
		if(cnt == 10 && i!=0) cout << "\n " ,cnt=0;
	}cout << '\n';
}
void bfs(node pos)
{
	queue<node> que;
	x1 = pos.gx+dir[pos.from][0];  y1 = pos.gy+dir[pos.from][1];
	que.push(node(x1,y1,pos.from));  d[x1][y1][pos.from] = 0;
	int cnt = 0;
	while(!que.empty())
	{
		node now = que.front();  que.pop();  
		if(now.gx == ex && now.gy == ey) {print(now);  return;}/*輸出路徑 */
		if(vis[now.gx][now.gy][now.from]) continue;
		vis[now.gx][now.gy][now.from] = 1;
		int k = now.from;  //原朝向
		for(auto v : g[now.gx][now.gy][k]) 
		{
			int u = (k+v+4)%4;  //新朝向 
			int x = now.gx + dir[u][0] ,y = now.gy + dir[u][1]; /*新座標 */
			if(x<1 || y<1 || x>9 || y>9 || !edge[x][y] || vis[x][y][u] || d[x][y][u]>=0) continue;
			que.push(node(x,y,u));  d[x][y][u] = d[now.gx][now.gy][now.from]+1;
			if(!fa[x][y][u].gx && !fa[x][y][u].gy ) fa[x][y][u] = now; /*紀錄第一次的，不然可能被蓋掉 */
		}
	}
	cout << " No Solution Possible\n"; 
}
int main()
{
	mp['E']=0;  mp['S']=1;  mp['W']=2;  mp['N']=3;
	mp['L']=-1;  mp['R']=1;  mp['F'] = 0;
	while(getline(cin,name))
	{
		memset(fa,0,sizeof(fa));  memset(d,-1,sizeof(d));
		for(int i=0 ;i<10 ;i++)
			for(int j=0 ;j<10 ;j++) for(int k=0 ;k<4 ;k++) g[i][j][k].clear();
		memset(edge,0,sizeof(edge)); memset(vis,0,sizeof(vis));
		if(name == "END") break;
		cin >> sx >> sy;
		cin >> st;  
		cin >> ex >> ey; /*起、終點*/
		edge[sx][sy] = edge[ex][ey] = 1;
		int x ,y;
		while(cin >> x && x)
		{
			cin >> y;  edge[x][y] = 1;
			while(cin >> s)
			{
				if(s == "*") break;
				for(int i=1 ;i<s.size() ;i++) g[x][y][mp[s[0]]].pb(mp[s[i]]) ;
			}
		}
		printf("%s\n ",name.c_str());
		bfs(node(sx ,sy ,mp[st]));
		getchar(); 
	} 
	return 0;
}