题解 | 象棋马走步问题

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

bool obstacle[64] = {false};
bool visited[64];
int pre[64];

int dx[8] = {2, 1, -1, -2, -2, -1, 1, 2};
int dy[8] = {-1, -2, -2, -1, 1, 2, 2, 1};

struct Pos{
    int x;
    int y;
    Pos(int a, int b) : x(a), y(b){}
};

Pos to2pos(int n){
    return Pos(n / 8, n % 8);
}

int to1pos(int x, int y){
    return x * 8 + y;
}

bool isvalid(int x, int y){
    return x >= 0 && x < 8 && y >= 0 && y < 8 && !obstacle[to1pos(x, y)];
}

// 比较函数：用于对路径进行排序
bool comparePaths(const vector<int>& a, const vector<int>& b) {

    for (int i = 0; i < a.size(); i++) {
        if (a[i] != b[i]) {
            return a[i] < b[i];
        }
    }
    return false;
}

vector<vector<int>> bfs_all_paths(int startpos, int endpos){
    memset(visited, false, sizeof(visited));
    memset(pre, -1, sizeof(pre));

    // 记录每个节点的最短距离
    int dist[64];
    memset(dist, -1, sizeof(dist));

    queue<int> q;
    q.push(startpos);
    visited[startpos] = true;
    dist[startpos] = 0;

    while(!q.empty()){
        int current = q.front();
        q.pop();

        int x = to2pos(current).x;
        int y = to2pos(current).y;

        for(int i = 0; i < 8; i++){
            int newx = x + dx[i];
            int newy = y + dy[i];
            int newpos = to1pos(newx, newy);

            if(isvalid(newx, newy)){
                if(dist[newpos] == -1){
                    // 第一次访问该节点
                    dist[newpos] = dist[current] + 1;
                    pre[newpos] = current;
                    q.push(newpos);
                }
            }
        }
    }

    // 使用DFS回溯所有最短路径
    vector<vector<int>> allPaths;
    if(dist[endpos] == -1) return allPaths;  // 无法到达

    vector<int> path;
    function<void(int)> dfs = [&](int pos) {
        path.push_back(pos);

        if(pos == startpos) {
            vector<int> validPath = path;
            reverse(validPath.begin(), validPath.end());
            allPaths.push_back(validPath);
        }
        else {
            int x = to2pos(pos).x;
            int y = to2pos(pos).y;

            // 查找所有可能的前驱
            for(int i = 0; i < 8; i++) {
                int prevx = x - dx[i];
                int prevy = y - dy[i];
                if(prevx >= 0 && prevx < 8 && prevy >= 0 && prevy < 8 && !obstacle[to1pos(prevx, prevy)]) {
                    int prevpos = to1pos(prevx, prevy);
                    if(dist[prevpos] == dist[pos] - 1) {
                        dfs(prevpos);
                    }
                }
            }
        }

        path.pop_back();
    };

    dfs(endpos);
    return allPaths;
}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        int pos;
        cin >> pos;
        obstacle[pos] = true;
    }

    int startpos, endpos;
    cin >> startpos >> endpos;

    vector<vector<int>> allPaths = bfs_all_paths(startpos, endpos);

    if(allPaths.empty()){
        cout << "UNREACHED" << endl;
    }
    else{
        // 对路径进行排序
        sort(allPaths.begin(), allPaths.end(), comparePaths);

        for(int i = 0; i < allPaths.size(); i++){
            for(int j = 0; j < allPaths[i].size(); j++){
                cout << allPaths[i][j] << " ";
            }
            cout << endl;
        }
    }

    return 0;
}

这b题难成啥了 完全不会