题目描述

N皇后问题

样例

1
8
5
0

1
92
10

C++ 代码（会超时，需打表和acwing843思路一样）

#include<iostream>
using namespace std;

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

void dfs(int u) {
    if(u==n) {
        k++;
        return;
    }

    for(int i=0; i<n; i++)
        if(!col[i]&&!dg[u+i]&&!udg[n-u+i]) {
            col[i]=dg[u+i]=udg[n-u+i]=true;

            dfs(u+1);

            col[i]=dg[u+i]=udg[n-u+i]=false;
        }

}

int main() {

    while(cin >> n) {
        if(n == 0) break;
        k = 0;
        dfs(0);

        cout << k << endl;
    }
    return 0;

}

C++ 代码2

#include<iostream>
using namespace std;

int n,t;
int m[11];

void dfs(int a) {
    int flag;
    if(a==n+1) {
        t++;
        return;
    } else {
        for(int i=1; i<=n; ++i) {
            m[a]=i;
            flag=1;
            for(int j=1; j<a; ++j) {
                if(m[j]==i||i-a==m[j]-j||i+a==m[j]+j) {
                    flag=0;
                    break;
                }
            }
            if(flag)    dfs(a+1);
        }
    }
}

int main() {
    int N;
    int ans[11];

    for(n=1; n<=10; ++n) {
        t=0;
        dfs(1);
        ans[n]=t;
    }

    while(~scanf("%d",&N)) {
        if(N == 0) break;
        printf("%d\n",ans[N]);
    }

    return 0;
}