题目描述

给出一个n×nn\times nn×n的国际象棋棋盘，你需要在棋盘中摆放nnn个皇后，使得任意两个皇后之间不能互相攻击。具体来说，不能存在两个皇后位于同一行、同一列，或者同一对角线。请问共有多少种摆放方式满足条件。

输入描述: 

一行，一个整数n，表示棋盘的大小。

输出描述: 

输出一行一个整数，表示总共有多少种摆放皇后的方案，使得它们两两不能互相攻击。
这个题目也算是一个比较典的dfs问题，我不太会dfs。
本题就是按行去搜索，对于每次搜索，需要先判断对应的列，对角线是否能放，所以我们使用数组lie[]，l[],r[]去标记同一列和统一对角线已经被访问了。对于左对角线，可以发现x-y相同，所以每次访问我们标记了l[x-y+n]，加上n是为了防止出现负数。右对角线也是累死。
需要注意的是，我们搜索完下一行时，需要恢复状态。 
#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N = 1e3 + 10;
const int mod  = 1e9 + 7;
/**
 * 不要使用#define int long long
 * 不开long long见祖宗
 *                  ----YuFei Zhou
 */
int n;
int lie[50],l[50],r[50];    //判断列/左对角线/右对角线
/**
 * 同一个左对角线的x-y为定值我们加n防止为负数
 * 右对角线也是如此
 */
int ans;
void dfs(int x){
    if(x > n){
        ans++;
        return;
    }
    for (int i = 1; i <= n; ++i) {  //按行去搜索
        if(lie[i] == 0 && l[x-i+n] == 0 && r[x+i] == 0){
            lie[i] = 1;
            l[x-i+n] = 1;
            r[x+i] = 1;
            dfs(x+1);   //搜索下一行
            lie[i] = 0; //搜索完恢复状态
            l[x-i+n] = 0;
            r[x+i] = 0;
        }
    }
}
void solve(){
    cin>>n;
    dfs(1);
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();//1 2 3 4 5
    }
    return 0 ;
}