当前位置：首页 > article >正文

图论 n 皇后问题

article 2025/1/23 8:33:15

首先是对角线的英文是 diagonal ，注意线性代数里面说的主对角线是从左上到右下的这条对角线。有时候我们看题解，总是被一些比较小的点卡住。这个小的点可能不是这个题的关键，但是这个小点理解不了就做不了这个题。写算法题或者写其他的题都经常面临这个问题。我能做的就是多多鼓励自己，然后多多练习。

#include<iostream>

using namespace std;

const int N=20;
bool col[N],dg[N],udg[N];
int n;
char g[N][N];

void dfs(int u){
    if(u==n){
        for(int i=0;i<n;i++){
            puts(g[i]);
        }
        puts("");
        return ;
    }
    
    for(int i=0;i<n;i++){
        if(!col[i]&&!dg[u+i]&&!udg[n+i-u]){
            g[u][i]='Q';
            col[i]=dg[u+i]=udg[n+i-u]=true;
            dfs(u+1);
            col[i]=dg[u+i]=udg[n+i-u]=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;
}