【dfs基础题】洛谷P1219题解

题目大意

给定棋盘的规格为 \(n×n\)，现在要摆 \(n\) 个皇后，使得每个皇后不能互相攻击。

题目解答

由题意可知，如果两个皇后在同一行或同一列或同一对角线，那么就会互相攻击。

那么就简单了，若当前要摆的是第 \(i\) 个皇后，那么只需要 for 循环一遍前面的 \(i-1\) 个皇后，判断前面的皇后会不会和第 \(i\) 个皇后互相攻击。

我们已经知道行数都都是固定的，我们只要判断两个皇后是否在同一列或同一对角线即可。

记当前第 \(i\) 个皇后在第 \(h\) 行第 \(l\) 列、前面的 \(i-1\) 个皇后的列数都放在了 \(a\) 数组，接下来来看怎么判断：

• 列：这个比较简单，只要前面的 \(i-1\) 个皇后都不满足

for(int j=1;j<=i-1;j++){
	if(a[j]==l)
}

那么就代表这两个皇后不在同一列；

• 对角线：对角线我们可以画一个棋盘，然后标记一下对角线所在的行和列，就会发现规律，如果前面的 \(i-1\) 个皇后都不满足

for(int j=1;j<=i-1;j++){
	if(abs(h-j)==abs(l-a[j]))
}

那么就代表两个皇后不在同意对角线。

代码

#include<bits/stdc++.h>
using namespace std;
int n,sum,a[110];
int awa(int h,int l){
	int i;
	for(i=1;i<=h-1;i++)
		if((l==a[i])||(abs(h-i)==abs(l-a[i])))return 0;//判断是否在同一列或同意对角线 
	return 1;
}
void queen(int qwq){
	int i;
	if(qwq>n){
		sum++;
		if(sum<=3){//前三组输出 
			for(i=1;i<=n;i++)cout<<a[i]<<" ";
			cout<<endl;
		}else return;
	}
	for(i=1;i<=n;i++){
		if(awa(qwq,i)==1){//当前皇后和前面的皇后不会互相攻击 
			a[qwq]=i;/*摆下当前皇后*/queen(qwq+1);/*继续来到下一列放置皇后*/a[qwq]=0;/*回溯*/
		}
	}
}
int main(){
	cin>>n;	
	queen(1);
	cout<<sum<<endl;
	return 0;
}