• 题意

题目链接：https://www.luogu.com.cn/problem/P1219?contestId=130784

题意就是给一个 N x N 的矩阵，然后放 N 个皇后，问可以怎么放，有多少种放法。

• 思路

dfs。
需要三个数组，col[i] 用来存第 i 列是否放置了皇后，dg[i] 用来存对角线 i 是否放置了皇后，udg[i] 用来存反对角线 i 是否放置了皇后。
然后思路的话就是一行一行搜，比如说搜到了第 u 行，那么我们从左到右遍历一下，上面三个数组都放了皇后没，如果没放，那就把它放上去。有一个难点就是怎么判断对角线和反对角线，对角线就是 u + i ，至于原因就是因为这是一个正方形，然后关于对角线对称，所以你如果把一个点的行数加上列数，那么这一定就是一条对角线。同理反对角线就是 u - i + n，为什么要加 n ，因为防止出现负数嘛，行数又不一定大于列数。

• 代码

#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#define endl '\n'
//#define int long long
using namespace std;
typedef long long ll; 
typedef pair<int, int> PII;
const int N = 100;
int n, m, k;
bool col[N], dg[N], udg[N];
vector<int> v;

void dfs(int u){
    if (u == n+1){
        k ++;
        if (k <= 3){
            for (auto t : v)cout << t << ' ';
            cout << endl;
        }
        return;
    }

    for (int i = 1; i <= n; i ++){
        if (!col[i] && !dg[u+i] && !udg[u-i+n]){
            col[i] = dg[u+i] = udg[u-i+n] = true;
            v.push_back(i);
            dfs(u+1);
            col[i] = dg[u+i] = udg[u-i+n] = false;
            v.pop_back();
        }
    }
    return;
}

void sovle(){
    cin >> n;
    dfs(1);
    cout << k << endl;
}

int main()
{
    int t = 1; 
    //scanf("%d", &t);

    while (t --){
         sovle();
    }

    return 0;
}