-
题意
题目链接：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;
}