题解 | 象棋马走步问题

#include <stdio.h>
#include <vector>
#include <unordered_set>
using namespace std;

int n;
int min_path_len=64;
unordered_set<int>block;
unordered_set<int>visited;
vector<int> path;
vector<vector<int>>path_list;


vector<int> legal_move(int i){
    vector<int> legal_moves;
    legal_moves.clear();
    if(i-2*8>=0) {  //下行2格
        if (i%8 - 1 >= 0&&i - 2 * 8 - 1>=0&&block.find(i - 2 * 8 - 1)==block.end()) {  //左行1格
            legal_moves.push_back(i - 2 * 8 - 1);
        }
        if (i%8 + 1 < 8&&block.find(i - 2 * 8 + 1)==block.end()) {  //右行1格
            legal_moves.push_back(i - 2 * 8 + 1);
        }
    }
    if(i%8-2>=0) {  //左行2格
        if (i - 8 - 2 >= 0 && block.find(i - 8 - 2) == block.end()) {  //下行一格
            legal_moves.push_back(i - 8 - 2);
        }
    }
    if(i%8+2<8) {  //右行2格
        if (i - 8 >= 0 && block.find(i - 8 + 2) == block.end()) {  //下行一格
            legal_moves.push_back(i - 8 + 2);
        }
    }
    if(i%8-2>=0){  //左行2格
        if(i+8<64&&block.find(i + 8 - 2)==block.end()) {  //上行1格
            legal_moves.push_back(i + 8 - 2);
        }
    }
    if(i%8+2<8){  //右行2格
        if(i+8+2<64&&block.find(i + 8 + 2)==block.end()) {  //上行1格
            legal_moves.push_back(i + 8 + 2);
        }
    }
    if(i+2*8<64){  //上行2格
        if(i%8-1>=0&&block.find(i+2*8-1)==block.end()){  //左行1格
            legal_moves.push_back(i+2*8-1);
        }
        if(i%8+1<8&&i+2*8+1<64&&block.find(i+2*8+1)==block.end()){  //右行1格
            legal_moves.push_back(i+2*8+1);
        }
    }
    return legal_moves;
}

void find_path(int source,int target){
    if(path.size()>=min_path_len-1){
        return;
    }
    vector<int> legal_moves;
    legal_moves.clear();
    path.push_back(source);
    visited.insert(source);
    legal_moves = legal_move(path.back());
    for(int i=0;i<legal_moves.size();i++){
        if(visited.find(legal_moves[i])==visited.end()){
            if(legal_moves[i]==target){
                path.push_back(target);
                if(path.size()<min_path_len){
                    min_path_len = path.size();
                    path_list.clear();
                }
                path_list.push_back(path);
                path.pop_back();
                break;
            }
            else {
                find_path(legal_moves[i],target);
            }
        }
    }
    visited.erase(source);
    path.pop_back();

}
int main() {
    while(scanf("%d",&n)!=EOF){
        block.clear();
        path_list.clear();
        path.clear();
        visited.clear();
        min_path_len = 64;
        int a;
        for(int i=0;i<n;i++){
            scanf("%d",&a);
            block.insert(a);
        }
        int source, target;
        scanf("%d%d",&source,&target);
        // 边界校验
        if (source < 0 || source >= 64 || target < 0 || target >= 64) {
            printf("UNREACHED\n");
            continue;
        }
        if (block.count(source) || block.count(target)) {
            printf("UNREACHED\n");
            continue;
        }
        if (source == target) {
            printf("%d\n", source);
            continue;
        }
        find_path(source,target);
        if(path_list.empty()){
            printf("UNREACHED\n");
        }
        else{
            for(int i=0;i<path_list.size();i++){
                for(int j=0;j<path_list[i].size();j++){
                    printf("%d ",path_list[i][j]);
                    }
                printf("\n");
            }
        }
    }
}