H15342657960 @ 2024-11-15 11:14:11
#include<stdio.h>
#include<stdbool.h>
int cnt=0;
int next(int *p,int len,int step,int book[]);
int judge(int *p,int len);
int main()
{
int n;
scanf("%d",&n);
int map[n][n];
int book[n];
int *p=&map[0][0];
for(int i=0;i<n;i++)
{
book[i]=0;
for(int j=0;j<n;j++)
{
map[i][j]=0;
}
}
//printf("0");
next(p,n,0,book);
printf("%d",cnt);
}
int next(int *p,int len,int step,int book[])//深搜
{
//printf("step=%d\n",step);
if(judge(p,len))goto aa;//剪枝
if(step==len){
//printf("sss\t");
cnt++;if(cnt>3)goto aa;
for(int i=0;i<len;i++)
{
printf("%d ",book[i]);
}
printf("\n");
goto aa;
}
for(int i=0;i<len;i++)
{
*(p+step*len+i)=1;
book[step]=i+1;
next(p,len,step+1,book);
*(p+step*len+i)=0;
}
aa:;
}
int judge(int *p,int len)
{
int j=1;
bool flag1=false,flag2=false,flag3=false,flag4=false;
for(int i=0;i<len;i++)
{
flag1=false,flag2=false,flag3=false,flag4=false;
for(int j=0;j<len-i;j++)
{
//printf("%d %d\n",*(p+(i+j)*len+j),*(p+j*len+j+i));
if(*(p+(i+j)*len+j)==1&&flag1==false)flag1=true;
else if(*(p+(i+j)*len+j)==1&&flag1==true)
{
j=0;
break;
}
if(*(p+j*len+j+i)==1&&flag2==false)flag2=true;
else if(*(p+j*len+i+j)==1&&flag2==true)
{
j=0;
break;
}
if(*(p+(i+j)*len+len-1-j)==1&&flag3==false)flag3=true;
else if(*(p+(i+j)*len+len-1-j)==1&&flag3==true)
{
j=0;
break;
}
if(*(p+j*len+len-1-i-j)==1&&flag4==false)flag4=true;
else if(*(p+j*len+len-1-i-j)==1&&flag4==false)
{
j=0;
break;
}
}
}
//printf("%d\n",j);
return !j;
}by laotingrui @ 2024-11-17 20:43:12
@H15342657960 \ 看看我的 求关~~
#include<iostream>
using namespace std;
int n,sum;
int a[15];
bool b[15],c[30],d[30];
void dfs(int k){
if(k>n){ //放满n个
sum++;//增加一种解
if(sum<=3){//小于三，输出
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
cout<<endl;
}
}
else{
for(int i=1;i<=n;i++)
if(!b[i]&&!c[k+i]&&!d[k-i+13]){//判断行、主对角线、副对角线无冲突
a[k]=i;//放在第i列
b[i]=c[k+i]=d[k-i+13]=1;//标记为已放过
dfs(k+1);
b[i]=c[k+i]=d[k-i+13]=0;//回溯
}
}
}
int main(){
cin>>n;
dfs(1);
cout<<sum;
return 0;
}