一、题意

给出一个比较复杂的道路。每个结点有通行方向的限定。
输入起点、起点方向、终点，要求出最短路径并打印出路径。

二、解析

这是一道比较复杂的bfs题目。最主要是的要找清楚状态点是什么。在本题中，状态点是包含（x, y, dir）的3维点。因此在维护vis数组、父节点p数组、下一步方向的vec数组都需要是3维的。
此外对于向右转、向左转等旋转操作，可以通过一个如代码中getNext()中实现的方法。
然后关于打印路径，只要维护好了p数组，只要在最后写个while循环将p数组中的点链转存到vector中即可，然后就可以逆序打印出路径了。

三、代码

#include <iostream>
#include <string>
#include <queue>
#include <cstring>
using namespace std;
const string direction = "NESW";
const int Fx[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
struct node {
    int x, y, dir;
    node() {}
    node(int x, int y, int dir) : x(x), y(y), dir(dir) {}
} p[15][15][5];
int x0, y0, dir0, xt, yt;
bool vis[15][15][5];
string vec[15][15][5];

void clear() {
    memset(vis, 0, sizeof(vis));
    memset(p, 0, sizeof(p));
    for(int i = 0; i < 15; i ++) {
        for(int j = 0; j < 15; j ++) {
            for(int k = 0; k < 5; k ++) vec[i][j][k].clear();
        }
    }
}

node getNext(const node& u, char ch) {
    int dir;
    if(ch == 'F') dir = u.dir;
    else if(ch == 'R') dir = (u.dir + 1) % 4;
    else dir = (u.dir + 3) % 4;
    return node(u.x + Fx[dir][0], u.y + Fx[dir][1], dir);
}

void bfs(int x, int y, int dir) {
    queue<node> que;
    que.push(node(x, y, dir));
    vis[x][y][dir] = 1;
    p[x][y][dir] = node(-1, -1, -1);
    bool ok = 0;
    int dirt;
    while(!que.empty()) {
        node u = que.front();
        que.pop();
        if(u.x == xt && u.y == yt) {
            ok = 1, dirt = u.dir;
            break;
        }
        for(auto ch : vec[u.x][u.y][u.dir]) {
            node v = getNext(u, ch);
            // cout << "("<<u.x<<", "<<u.y<<", "<<direction[u.dir]<<") --> ch == "<<ch 
            // << "--> ("<<v.x<<", "<<v.y<<", "<<direction[v.dir]<<") "<<endl;
            if(vis[v.x][v.y][v.dir]) continue;
            que.push(v);
            vis[u.x][u.y][u.dir] = 1;
            p[v.x][v.y][v.dir] = u;
        }
    }
    if(!ok) cout << "  No Solution Possible" << endl;
    else {
        vector<node> tmp;
        int x = xt, y = yt, dir = dirt;
        do {
            tmp.push_back(node(x, y, dir));
            node next = p[x][y][dir];
            x = next.x, y = next.y, dir = next.dir;
        } while(x != -1);
        tmp.push_back(node(x0, y0, dir0));
        for(int i = tmp.size() - 1, cnt = 0; i >= 0; i --) {
            if(cnt == 0) cout << " ";
            node & cur = tmp[i];
            cout << " (" << cur.x << "," << cur.y << ")";
            cnt ++;
            if(i == 0) cout << endl;
            else if(cnt == 10) cout << endl, cnt = 0;
        }
    }
}

int main() {
    string name;
    while(cin >> name && name != "END") {
        clear();
        char ch0;
        cin >> x0 >> y0 >> ch0 >> xt >> yt;
        dir0 = direction.find(ch0);
        int x, y;
        string str;
        while(cin >> x && x) {
            cin >> y;
            while(cin >> str && str != "*") {
                int dir = direction.find(str[0]);
                vec[x][y][dir] = str.substr(1);
            }
        }
        cout << name << endl;
        bfs(x0 + Fx[dir0][0], y0 + Fx[dir0][1], dir0);
    }
}

四、归纳

  • bfs问题要先想清楚“状态点”如何定义，然后维护相应维度的vis、vec数组。
  • 如果需要打印路径需要用p数组进行父节点的存储。
  • debug时不要太着急，可以将打印信息写的详细一点，这样才能有利于更快地发现问题！就像代码中注释部分所示，花不了多长时间的。