题解 | #八皇后#

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
vector<string>res;
int Q[8][8]={0};
bool isValid(int row,int col){
    int i,j;
    for(i=0;i<8;i++){
        if(Q[i][col])return false;
    }
    for(i=row,j=col;i>=0&&j>=0;i--,j--){
        if(Q[i][j])return false;
    }
    for(i=row,j=col;i>=0&&j<8;i--,j++){
        if(Q[i][j])return false;
    }
    return true;
}
void backtracking(int row,string temp){
    if(temp.length()==8){
        res.push_back(temp);
        return;
    }
    for(int i=0;i<8;i++){
        if(isValid(row, i)){
            Q[row][i]=1;
            char c=i+1+'0';
            temp.push_back(c);
            backtracking(row+1,temp);
            Q[row][i]=0;
            temp.pop_back();//这一步很重要（回退）
        }
    }
}
int main() {
    int  b;
    string temp="";
    backtracking(0, temp);
    sort(res.begin(),res.end());
    while (cin  >> b) { // 注意 while 处理多个 case
        cout << res[b-1] << endl;
    }
}
// 64 位输出请用 printf("%lld")