题解 | #八皇后#

#include <iostream>
#include <vector>
using namespace std;
//同一斜对角线皇后行差值绝对值等于列差值绝对值
vector<int> pos(9);//八个皇后的列位置,下标代表第几行皇后
vector<string> allStr;//dfs的过程确保了自动有序
bool judge(int row,int& choice){
    for(int i=1;i<row;i++){//遍历前row-1个皇后的列位置
        if(pos[i]==choice) return false;//同列
        if(abs(row-i)==abs(choice-pos[i])) return false;//左上对角线，右上对角线（不可能有其他情况）
    }
    return true;
}
void dfs(int row,string& str){
    if(row>8){
        allStr.emplace_back(str);
        return;
    }
    for(int col=1;col<=8;col++){
        if(judge(row,col)){
            pos[row] = col;
            str+=(col+'0');
            dfs(row+1,str);
            str.erase(str.end()-1);
        }
    }
    return;
}
int main() {
    int n;
    string str="";
    dfs(1,str);
    while (cin >> n) {
        cout<<allStr[n-1]<<endl;
    }
}