【解题报告】洛谷P1219 八皇后

题目链接

https://www.luogu.com.cn/problem/P1219

思路

这个的话，直接搜索吧

唯一需要注意的就是如何表示行或者列，或者对角线已经被选择了

其中对角线就直接加起来就好了

另一条对角线就直接用一个新的数组，然后也转化成相加相等的形式就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int maxn=30;
int n;
int cnt;
bool hang[maxn],lie[maxn],dj[maxn],dj2[maxn];
int rec[maxn];
void dfs(int x)
{
	if(x==n)
	{
		cnt++;
		if(cnt<=3)
		{
			for(int i=1;i<=n;i++)
			cout<<rec[i]<<" ";
			cout<<'\n';
			return ;
		}
		return ;
	}
	for(int i=1;i<=n;i++)
	{
		if(lie[i]||dj[x+1+i]||dj2[x+1+(n-i)]) continue;
		lie[i]=true;
		dj[x+1+i]=true;
		dj2[x+1+(n-i)]=true;
		rec[x+1]=i;
		dfs(x+1);
		rec[x+1]=0;
		dj2[x+1+(n-i)]=false;
		dj[x+1+i]=false;
		lie[i]=false;
	}
}
int main()
{
	cin>>n;
	dfs(0);
	cout<<cnt<<'\n';
	return 0;
}