sakura_erii @ 2023-09-20 23:23:26
#include<bits/stdc++.h>
using namespace std;
#define MAX 100
int used1[MAX],used2[MAX],used3[MAX],n,ans=0,a[1000];//used1记录行的状态,used2记录(x,y)上面的斜线,used3记录下面的斜线
void dfs(int x) //x表示第x行的皇后放在哪里 每行有且仅有一个皇后
{
if(x>n)//证明全部排满,输出解
{
ans++;//排列个数
if(ans<=3)//输出前三个解,dfs函数保证了字典序
{
for(int i=1;i<=n;i++)
{
cout<<a[i]<<' ';
}
cout<<endl;
}
return;//不return见祖宗
}
for(int i=1;i<=n;i++)//枚举了所有的列
{
if(used1[i]==0 && used2[x+i]==0 && used3[x-i+15]==0)//i判断列,x+i是上面的斜线,x-i是下面的,加15防止越界
{
a[x]=i;//保存一遍结果
used1[i]=1,used2[x+i]=1,used3[x-i+15]=1;//记录不能放
dfs(x+1);//搜索下一行
used1[i]=0,used2[x+i]=0,used3[x-i+15]=0;//回溯
}
}
}
int main()
{
cin>>n;
dfs(1);
cout<<ans;
return 0;
}
by sakura_erii @ 2023-09-20 23:24:01
把MAX改成100,就过了
by sakura_erii @ 2023-09-20 23:25:35
原代码MAX 15,输出来4个结果,都是符合要求的,但是最后的ans是0,不到为啥,求助悬关
by JT_dw_ @ 2023-09-20 23:48:15
@sakura_erii used2[MAX],used3[MAX]
都溢出了啊,因为行数加列数大于 15 了