题意：迷宫从起点走到终点，进入某点的朝向不同，可以出去的方向也不同，输出最短路。
分析：因为朝向决定接下来在该点可以往哪里走，所以每个点需要有三个信息：x,y,d(坐标和进入该点的朝向)，所以将起点的下一个点当做初始状态
注意理解题意:进入交叉点的朝向与从哪个方向进交叉点正好相反
#pragma comment(linker, "/STACK:102400000, 102400000") #include<cstdio> #include<cstring> #include<cstdlib> #include<cctype> #include<cmath> #include<iostream> #include<sstream> #include<iterator> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<stack> #include<deque> #include<queue> #include<list> #define Min(a, b) ((a < b) ? a : b) #define Max(a, b) ((a < b) ? b : a) typedef long long ll; typedef unsigned long long llu; const int INT_INF = 0x3f3f3f3f; const int INT_M_INF = 0x7f7f7f7f; const ll LL_INF = 0x3f3f3f3f3f3f3f3f; const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f; const int dr[] = {0, 1, 0, -1}; const int dc[] = {1, 0, -1, 0}; const int MOD = 1e9 + 7; const double pi = acos(-1.0); const double eps = 1e-8; const int MAXN = 10000 + 10; const int MAXT = 10000 + 10; using namespace std; char s[30]; bool edge[15][15][5][5]; int dis[15][15][5]; const char* a = "ESWN";//与数组dr,dc方向对应 const char* b = "LFR"; struct Node{ int x, y, d;//当前点的坐标，及进入该点的朝向 Node(){} Node(int xx, int yy, int dd):x(xx), y(yy), d(dd){} }num[15][15][5];//记录该点的上一个点 int dir_id(char c){ return strchr(a, c) - a; } int turn_id(char c){ return strchr(b, c) - b; } bool judge(int x, int y){ return x >= 1 && x <= 9 && y >= 1 && y <= 9; } Node next(const Node&t, int turn){//turn与字符数组b下标对应 int dir = t.d;//向前走朝向不变 if(!turn){//向左走 dir = (dir + 3) % 4;//减1等价于加3 } else if(turn == 2){ dir = (dir + 1) % 4; } return Node(t.x + dr[dir], t.y + dc[dir], dir); } void print_ans(Node t, int tx, int ty, int dir){ stack<Node> st; while(1){ st.push(t); if(dis[t.x][t.y][t.d] == 0) break; t = num[t.x][t.y][t.d]; } st.push(Node(tx, ty, dir)); int cnt = 0; while(!st.empty()){ Node tmp = st.top(); st.pop(); ++cnt; if(cnt % 10 == 1) printf(" "); printf(" (%d,%d)", tmp.x, tmp.y); if(cnt % 10 == 0) printf("\n"); } if(cnt % 10 != 0) printf("\n"); } bool bfs(int sx, int sy, int dir, int ex, int ey){ memset(dis, -1, sizeof dis); queue<Node> q; q.push(Node(sx, sy, dir)); dis[sx][sy][dir] = 0; int tx = sx - dr[dir];//迷宫起点 int ty = sy - dc[dir]; while(!q.empty()){ Node t = q.front(); q.pop(); if(t.x == ex && t.y == ey){ print_ans(t, tx, ty, dir); return true; } for(int i = 0; i < 3; ++i){ Node v = next(t, i); if(edge[t.x][t.y][t.d][i] && judge(v.x, v.y) && dis[v.x][v.y][v.d] < 0){ dis[v.x][v.y][v.d] = dis[t.x][t.y][t.d] + 1; num[v.x][v.y][v.d] = t; q.push(v); } } } return false; } int main(){ while(scanf("%s", s) == 1){ if(strcmp(s, "END") == 0) return 0; printf("%s\n", s); memset(edge, 0, sizeof edge); int sx, sy, ex, ey; char dir; scanf("%d%d %c%d%d", &sx, &sy, &dir, &ex, &ey); int d = dir_id(dir);//进起点的下一个点的朝向 int nx = sx + dr[d];//起点的下一个位置 int ny = sy + dc[d]; int x; while(scanf("%d", &x) == 1){ if(x == 0) break; int y; scanf("%d", &y); while(scanf("%s", s) == 1){ if(s[0] == '*') break; int tmp_dir = dir_id(s[0]); int len = strlen(s); for(int i = 1; i < len; ++i){ int tmp_turn = turn_id(s[i]); edge[x][y][tmp_dir][tmp_turn] = 1; } } } bool ok = bfs(nx, ny, d, ex, ey);//起点的下一个点因为已知，所以将其当为开始的点 if(!ok){ printf(" No Solution Possible\n"); } } return 0; }