UVA 816 — Abbott’s Revenge(BFS求最短路)
有一个 9 * 9 的交叉点的迷宫。 输入起点， 离开起点时的朝向和终点， 求最短路（多解时任意一个输出即可）。进入一个交叉点的方向（用NEWS表示不同方向）不同时， 允许出去的方向也不相同。 例如：1 2 WLF NR ER * 表示如果 进去时朝W（左）， 可以 左转（L）或直行（F）， 如果 朝N只能右转（R） 如果朝E也只能右转。* 表示这个点的描述结束啦！
输入有： 起点的坐标， 朝向， 终点的坐标。然后是各个坐标，和各个坐标点的情况（进去方向和可以出去的方向） 以*号表示各个坐标点描述的结束。
题目分析：本题和普通的迷宫在本质上是一样的， 但是由于“朝向”也起了关键的作用， 所以需要一个三元组（r，c, dir）表示位于（r， c）面朝dir 的状态。 假设入口位置为（r0，c0）朝向为dir ， 则初始状态并不是（r0， c0， dir）， 而是（r1， c1， dir）因为开始时他别无选择， 只有一个规定的方向。 其中， （r1， c1）是沿着方向dir走一步之后的坐标， dir刚好是他进入该点时的朝向。 此处用d[r][c][dir]表示初始状态到（r， c， dir）的最短路长度， 并且用 p[r][c][dir]保存了状态（r， c， dir）在BFS树中的父结点。
规律：： 很多复杂的迷宫问题都可以转化成最短路问题， 然后用BFS求解。 在套用BFS框架之前， 需要先搞清楚图中的“结点”包含哪些内容。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int r0,c0,r2,c2,r1,c1,dir;
const char *dirs = "NESW";
const char *turns = "FLR";
const int dr[] = {-,,,};
const int dc[] = {,,,-};
const int maxn = ;
int dir_id(char s){return strchr(dirs,s) - dirs;}
int turn_id(char s){return strchr(turns,s) - turns;}
int has_edge[maxn][maxn][][];// 表示当前状态（r，c，dir），是否可以沿着转弯方向[trun]行走。
struct Node{
int r,c,dir;
Node(int r=,int c=,int dir=):r(r),c(c),dir(dir) {}
};
int d[maxn][maxn][];///表示初始状态到(r,c,dir)的最短路径长度
Node p[maxn][maxn][];///用来记录从哪一步走到(r,c,dir)，即其父节点
///读入地图
bool read_input()
{
char s[],s2[];
if(scanf("%s%d%d%s%d%d",s,&r0,&c0,s2,&r2,&c2) != ) return false;
cout<<s<<endl;
dir = dir_id(s2[]);
r1 = r0 + dr[dir];
c1 = c0 + dc[dir];
memset(has_edge,,sizeof(has_edge));
for(;;)
{
int r,c;
cin>>r;
if( r == ) break;
cin>>c;
while(cin>>s && s[] != '*')
{
for(int i=;i<strlen(s);i++)///将当前路口（r,c），可以的前进方向存到has_edge中
has_edge[r][c][dir_id(s[])][turn_id(s[i])] = ;
}
}
return true;
}
///从当前节点u，转向为i，前进一步
Node walk(Node u,int i)
{
int temp = u.dir;
if(i == ) temp = (temp+)%;///逆时针旋转，L
if(i == ) temp = (temp+)%;///顺时针旋转，R
return Node(u.r + dr[temp],u.c + dc[temp],temp);
}
///判断是否出界
bool inside(int r,int c)
{
return r >= && r <= && c >= && c <= ;
}
///将结果进行打印
void print_ans(Node u)
{
vector<Node> nodes;
for(;;)
{
nodes.push_back(u);
if(d[u.r][u.c][u.dir] == ) break;
u = p[u.r][u.c][u.dir];
}
nodes.push_back(Node(r0,c0,dir));
///打印解，每行10个
int cnt = ;
for(int i=nodes.size()-;i>=;i--)
{
if(cnt % == ) printf(" ");
printf(" (%d,%d)",nodes[i].r,nodes[i].c);
if(++cnt % == ) cout<<endl;
}
if(nodes.size() % != ) cout<<endl;
}
///BFS
void solve()
{
queue<Node> q;
memset(d,-,sizeof(d));
Node u(r1,c1,dir);
d[u.r][u.c][u.dir] = ;
q.push(u);
while(!q.empty())
{
Node u = q.front();q.pop();
if(u.r == r2 && u.c == c2) {print_ans(u);return;}///到达终点
for(int i=;i<;i++)///3个方向，0-F,1-L,2-R
{
Node v = walk(u,i);//超当前方向走，下一个结点
if(has_edge[u.r][u.c][u.dir][i] ///1.判断是否能向当前方向走
&& inside(v.r,v.c)///2.判断是否出界
&& d[v.r][v.c][v.dir] < )///3.判断是否已经走过这条路 u->v
{
d[v.r][v.c][v.dir] = d[u.r][u.c][u.dir]+;
p[v.r][v.c][v.dir] = u;//记录父节点
q.push(v);
}
}
}
cout<<" No Solution Possible"<<endl;//走了所有可以走的可能， 无法到达终点
}
int main()
{
while(read_input())
{
solve();
} return ;
}
