N皇后问题
按行递归,按列枚举
对于当前位置是否可以放置用数组来判断是否可以放置
col判断第i列是否可以放置,dg代表对角线,udg代表反对角线
对角线可以表示为y=x+b,由于同一对角线上的b都相等,所以可以用b来判断对角线是否可以放置
由于数组下标不能为负数,所以b=y-x+n;加上一个偏移量n,使b恒为正数
反对角线y=-x+b;同理
由于枚举顺序是从小到大枚举,所以不用考虑字典序
最后用vector记录一下答案就好啦
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int maxn=30;
int n,cnt;
int col[maxn],dg[maxn],udg[maxn]; //col代表第i行是否放置棋子
vector<int> v;
void dfs(int x)
{
if(x==n)
{
if(cnt<3)
{
for(int i=0;i<v.size();i++) cout<<v[i]<<" ";
cout<<endl;
}
cnt++;
}
for(int i=0;i<n;i++)
{
if(!col[i]&&!dg[i-x+n]&&!udg[i+x])
{
v.push_back(i+1); //当前行放置的位置是第i+1列
col[i]=1; //标记
dg[i-x+n]=1;
udg[i+x]=1;
dfs(x+1);
v.pop_back(); //状态恢复
col[i]=0;
dg[i-x+n]=0;
udg[i+x]=0;
}
}
}
int main()
{
cin>>n;
dfs(0);
cout<<cnt<<endl;
return 0;
}
具体可以看y总视频讲解同类型题
https://www.acwing.com/video/275/