HDU-2553 N皇后

传送门：HDU - 2553

题目描述

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。

输入描述

共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。

输出描述

共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。

题意分析

棋盘问题，判断对角线就行了，这题直接交的话会TLE，所以得先打表。

样例输入

1
8
5
0

样例输出

1
92
10

AC代码

#include<bits/stdc++.h>
#pragma GCC optimize(2)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef map<int, int> mii;
typedef map<ll, ll> mll;

#define ull unsigned long long
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

const int maxn=1e6+10;
const ll mod=1e9+7;
const int INF = 0x3f3f3f3f;

int n,sum;
int a[12][12],vis[11];

bool judge(int x,int y) {
    int i,j,f=0;
    for(i=x+1,j=y+1; i!=n,j!=n; i++,j++) {
        if(a[i][j]==2) {
            f=1;
            break;
        }
    }
    for(i=x+1,j=y-1; i!=n,j!=-1; i++,j--) {
        if(a[i][j]==2) {
            f=1;
            break;
        }
    }
    for(i=x-1,j=y-1; i!=-1,j!=-1; i--,j--) {
        if(a[i][j]==2) {
            f=1;
            break;
        }
    }
    for(i=x-1,j=y+1; i!=-1,j!=n; i--,j++) {
        if(a[i][j]==2) {
            f=1;
            break;
        }
    }
    if(f)return false;
    else return true;
}

void dfs(int x,int y) {
    if(y==n) {
        sum++;
        return ;
    }
    for(int i=0; i<n; i++) {
        if(!vis[i]&& judge(x,i)) {
            a[x][i]=2;
            vis[i]=1;
            dfs(x+1,y+1);
            vis[i]=0;
            a[x][i]=0;
        }
    }
}

int main() {
    IOS;
    int x;
    for(int i=1; i<=10; i++) {
        n=i;
        sum=0;
        memset(a,0,sizeof(a));
        memset(vis,0,sizeof(vis));
        dfs(0,0);
        cout<<sum<<endl;
    }
}