每日单词——AcWing.1432. 棋盘挑战
2021-01-22
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;
}
标题:每日单词——AcWing.1432. 棋盘挑战
作者:xiaob0
地址:https://xiaobo.net.cn/articles/2021/01/22/1611319821131.html