【AcWing】843. n皇后问题

剪纸就是判断当前方案一定不合法了就不往下搜了，把这个枝减掉，直接回溯。

代码

#include<iostream>

using namespace std;

const int N=10;

int n;
char g[N][N];//棋盘
bool col[N],dg[N*2],udg[N*2];//分别代表 列 斜线 反斜线有没有占用，对角线个数为2n-1，开2n

void dfs(int u){//u是第几行
    if(u==n){
        for(int i=0;i<n;i++) puts(g[i]);
        printf("\n");
        return;
    }
    for(int i=0;i<n;i++){
        if(!col[i] && !dg[-u+i+n] && !udg[u+i]){
            g[u][i]='Q';
            col[i] = dg[-u+i+n] = udg[u+i] = true;
            dfs(u+1);//不做就剪枝了
            col[i] = dg[-u+i+n] = udg[u+i] = false;
            g[u][i]='.';
        }
    }
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            g[i][j]='.';
    dfs(0);
    return 0;
}