题意：
给出一个迷宫，在迷宫的节点处，面向某个方向只能向给定的方向转弯。给出起点和终点输出迷宫的最短路径，这里指的是刚刚离开起点的时刻，所以即使起点和终点重合路径也非空。
分析：
用三个变量来表示状态，r,c,dir，分别代表所处的位置和朝向。在输入数据的同时，也要初始化has_edge[r][c][dir][turn],代表处于(r, c, dir)这个状态时能否向turn转弯。
结构体数组p用来保存路径。
因为路径可能比较长，所以如果采用地轨输出的话，可能会栈溢出。代码中采用了动态数组来输出。
一直WA的原因：读入函数Input返回值是bool，而只在代码中写了return false; 却没有在最后加上 return true;
//#define LOCAL
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std; struct Node
{
int r, c;
int dir;
Node(int rr=, int cc=, int ddir=):r(rr), c(cc), dir(ddir) {}
}; const char* dirs = "NESW";
const char* turns = "FLR";
int dir_id(char c) { return strchr(dirs, c) - dirs; }
int turn_id(char c) { return strchr(turns, c) - turns; }
const int dr[] = {-, , , };
const int dc[] = {, , , -};
int d[][][];
Node p[][][];
int r0, c0, r1, dir, c1, r2, c2;
char name[], c[], s[];
bool has_edge[][][][]; bool inside(int r, int c)
{ return (r>= && r<= && c>= && c<=); } bool Input()
{
if(scanf("%s%d%d%s%d%d", name, &r0, &c0, &c, &r2, &c2)!=) return false;
printf("%s\n", name);
dir = dir_id(c[]);
r1 = r0 + dr[dir];
c1 = c0 + dc[dir]; memset(has_edge, false, sizeof(has_edge));
int a, b;
while(scanf("%d", &a))
{
if(a == ) break;
scanf("%d", &b);
while(scanf("%s", s))
{
if(s[] == '*') break;
int tempd = dir_id(s[]);
for(int i = ; i < strlen(s); ++i)
has_edge[a][b][tempd][turn_id(s[i])] = true;
}
}
return true;
} Node walk(const Node& u, int turn)
{
int dir = u.dir;
if(turn == ) dir = (dir + ) % ;
if(turn == ) dir = (dir + ) % ;
return Node(u.r + dr[dir], u.c + dc[dir], dir);
} 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)); int cnt = ;
for(int i = nodes.size()-; i >= ; --i)
{
if(cnt % == ) printf(" ");
printf(" (%d,%d)", nodes[i].r, nodes[i].c);
if(++cnt % == ) printf("\n");
}
if(nodes.size() % != ) printf("\n");
} void solve()
{
queue<Node> q;
memset(d, -, sizeof(d));
Node u(r1, c1, dir);
d[r1][c1][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)
{
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] < )
{
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);
}
}
}
puts(" No Solution Possible");
} int main(void)
{
#ifdef LOCAL
freopen("816in.txt", "r", stdin);
#endif while(Input())
{
solve();
} return ;
}
代码君