题解 | #八皇后#

sstream对象 <<读入类型的数据 >>读出类型的数据

/* DFS
 * 行从0到7逐层增加，不会存在重复放到同一行的情况
 * 列需要用bool col[8]记录某行是否已经放置
 * 对角线则需要用一个bool matrix[8][8](代码里用到矩阵名是djx)，并放到Judge(int x,int y)中判断
 * 然后思路就比较简单了，按照DFS对可扩展的状态进行递归
 * 每层的可扩展状态满足：
 *    （1）列上没有其它棋子
 *    （2）对角线上没有棋子
 * 好像把DFS中的now换成row更容易理解？
 */
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;
 
const int maxN = 8;
bool djx[maxN][maxN] = {false};
bool col[maxN] = {false};
 
vector<string> vi;        //可以用string
 
bool Judge(int x,int y){    //用于判断当前条件下（djx数组目前的状态下）对角线上是否已经有棋子了
    int y2 = y;
    for(int i=x;i>=0;i--){
        if(y>=0 && djx[i][y--]==true)
            return false;
        if(y2<8 && djx[i][y2++]==true)
            return false;
    }
    return true;
}
void DFS(int now,string ans){
    if(now==8){
        vi.push_back(ans);
        return ;
    }
    for(int j=0;j<8;j++){        //完全的DFS思路
        if(!col[j] && Judge(now,j)){
            col[j] = true;
            djx[now][j] = true;           //注意：题目里的所有数字都是从1开始计数，所以使用j+1记录answer
            stringstream ss;
            int n = j+1;
            ss<<n;
            DFS(now+1,ss.str()+ans);        //可以用string
            col[j] = false;
            djx[now][j] = false;
        }
    }
}
int main(){
    DFS(0,"");
    sort(vi.begin(),vi.end());      //对answer进行排序，string内置排序
    int index;
    while(cin>>index){
        cout<<vi[index-1]<<endl;    //注意题目中所有数字均为从1计数
    }
    return 0;
}