题解 | 象棋马走步问题

#include <algorithm>
#include <bits/stdc++.h>
#include <iterator>
#include <vector>
using namespace std;

int mov[8][2] {{1, -2}, {1, 2}, {-1, -2}, {-1, 2},
    {2, 1}, {2, -1}, {-2, 1}, {-2, -1}
};

void dfs(vector<vector<int>>& res, vector<int>& tmp, vector<vector<int>>& pre,
         int point, int st) {
    tmp.push_back(point);
    if (point == st) {
        vector<int> validtmp(tmp);
        reverse(validtmp.begin(), validtmp.end());
        res.push_back(validtmp);
    } else {
        for (int i = 0; i < pre[point].size(); i++) {
            dfs(res, tmp, pre, pre[point][i], st);
        }
    }
    tmp.pop_back();
}

int main() {
    int n;
    cin >> n;
    int graph[8][8] {0};
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        graph[x / 8][x % 8] = 1;
    }
    int st, en;
    cin >> st >> en;
    int stx = st / 8, sty = st % 8, enx = en / 8, eny = en % 8;
    if (graph[stx][sty] == 1 || graph[enx][eny] == 1) {
        cout << "UNREACHED" << endl;
        return 0;
    }

    int dist[64];
    memset(dist, -1, sizeof(dist));
    vector<vector<int>> pre(64);
    queue<pair<int, int>> q;
    dist[st] = 0;
    q.push({stx, sty});
    while (!q.empty()) {
        int ox = q.front().first, oy = q.front().second;
        int op = ox * 8 + oy;
        q.pop();
        for (int i = 0; i < 8; i++) {
            int nx = ox + mov[i][0], ny = oy + mov[i][1];
            if (nx < 0 || nx >= 8 || ny < 0 || ny >= 8) continue;
            if (graph[nx][ny] != 1) {
                int p = nx * 8 + ny;
                if (dist[p] == -1) {
                    dist[p] = dist[op] + 1;
                    pre[p].push_back(op);
                    q.push({nx, ny});
                } else {
                    if (dist[p] == dist[op] + 1)
                        pre[p].push_back(op);
                }

            }
        }
    }
    if (dist[en] == -1) {
        cout << "UNREACHED" << endl;
        return 0;
    }

    vector<vector<int>> res;
    vector<int> tmp;
    dfs(res, tmp, pre, en, st);

    sort(res.begin(), res.end());
    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[i].size(); j++) {
            if (j != 0) cout << ' ';
            cout << res[i][j];
        }
        cout << endl;
    }
}

bfs + dfs