题目链接：传送门
分析：很显然，这是一道BFS的题目，但是有很多的限制条件，这样的话处理就比较麻烦，那么要怎么处理呢?
首先，要用一个can数组来表示当前在(x,y),方向为dir，接下来要往i处转弯行不行，这个是题目告诉我们的，我们在读入的时候同时预处理一下就好了.然后BFS的时候要用三元组来表示状态(x,y,dir),因为影响答案的并不仅仅是坐标，还有当前状态的朝向.在每一步的时候枚举方向，下一步的坐标就能很好地推出来，这里要注意的是移动数组要和方向对应.
最后就是输出了，在BFS中每个状态记录这个状态的“父节点”--也就是上一状态，如果搜索到答案了，就从最后一个状态开始不断地向前推，一个一个输出就可以了,格式一定要注意，打错一个空格都会WA......
#include <queue> #include <vector> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const char *dirs = "NESW"; const char *turns = "FLR"; bool flag = true,can[11][11][5][5]; int sx, sy, tx, ty, fangxiang, x, y,d[11][11][5]; int dx[] = { -1, 0, 1, 0 }; int dy[] = { 0, 1, 0, -1 }; int dir_id(char ch) { return strchr(dirs, ch) - dirs; } int turn_id(char ch) { return strchr(turns, ch) - turns; } struct node { int x, y, dir; }fa[11][11][5]; bool fanwei(int x, int y) { if (x > 0 && x < 10 && y > 0 && y < 10) return true; return false; } node walk(node &u, int turn) { int di = u.dir; if (turn == 1) di = (di + 3) % 4; else if (turn == 2) di = (di + 1) % 4; node temp; temp.x = u.x + dx[di]; temp.y = u.y + dy[di]; temp.dir = di; return temp; } void print(node u) { vector<node> p; while (1) { p.push_back(u); if (d[u.x][u.y][u.dir] == 0) break; u = fa[u.x][u.y][u.dir]; } node temp; temp.x = x; temp.y = y; temp.dir = fangxiang; p.push_back(temp); int cnt = 0; for (int i = p.size() - 1; i >= 0; i--) { if (cnt % 10 == 0) cout << " "; cout << " (" << p[i].x << "," << p[i].y << ")"; if (++cnt % 10 == 0) cout << endl; } if (p.size() % 10 != 0) cout << endl; } void bfs() { queue <node> q; memset(d, -1, sizeof(d)); memset(fa, 0, sizeof(fa)); node temp; temp.x = sx; temp.y = sy; temp.dir = fangxiang; d[sx][sy][fangxiang] = 0; q.push(temp); while (!q.empty()) { node u = q.front(); q.pop(); if (u.x == tx && u.y == ty) { flag = 0; print(u); return; } for (int i = 0; i < 3; i++) { node v = walk(u, i); if (can[u.x][u.y][u.dir][i] && fanwei(v.x, v.y) && d[v.x][v.y][v.dir] < 0) { d[v.x][v.y][v.dir] = d[u.x][u.y][u.dir] + 1; fa[v.x][v.y][v.dir] = u; q.push(v); } } } } int main() { char ch[30]; while (scanf("%s", ch) && strcmp(ch, "END")) { printf("%s ", ch); flag = true; memset(can, 0, sizeof(can)); char s; cin >> x >> y >> s >> tx >> ty; fangxiang = dir_id(s); sx = x + dx[fangxiang]; sy = y + dy[fangxiang]; int r, c; char str[30]; while (scanf("%d", &r)) { if (r == 0) break; scanf("%d", &c); while (cin >> str) { if (str[0] == '*') break; int dID = dir_id(str[0]); for (int i = 1; i < strlen(str); i++) { int tID = turn_id(str[i]); can[r][c][dID][tID] = 1; } } } bfs(); if (flag) cout << " No Solution Possible" << endl; getchar(); } return 0; }