AcWing.1432. 棋盘挑战

题意：N皇后

思路：
主对角线满足
x1+y1==x2+y2
副对角线满足
x1-y1==x2-y2

代码

#include<bits/stdc++.h>

using namespace std;

vector<int>ans;
int n;
int l[20];
int h[20];
int cnt;

bool ok(int x,int y)
{
	for(int i=1;i<x;i++) {
		if((i-h[i]==x-y)||(i+h[i]==x+y)) return false;
	}
	return true;
}

void dfs(int x)
{
	//填到了第n+1个皇后 
	if(x>n) {
	//	puts("yes");
		cnt++;
		if(cnt<=3) {
			for(int i=0;i<ans.size();i++) {
				if(i) cout<<' ';
				cout<<ans[i];
			}
			puts("");
			return ;
		}
	}
	
	//枚举填第x个皇后
	for(int i=1;i<=n;i++) {
		//依次放到第i列
		if(!l[i]&&ok(x,i)) {
			l[i]=1;
			h[x]=i;
			ans.push_back(i);
			dfs(x+1);
			l[i]=0;
			h[x]=0;
			ans.pop_back();
		}	 
	} 
}

int main()
{
	cin>>n;
	dfs(1);
	cout<<cnt<<'\n';
	return 0;	
}