dfs,求调

魏蕴博 @ 2023-10-14 21:32:48

#include<bits/stdc++.h>
using namespace std;
int q[100],n,ans;
int b1[100],b2[100],b3[100];
void dfs(int x)
{
    if(x>n)
    ans++;
        if(ans<=3)
        {
            for(int i=1;i<=n;i++)
            {
                cout<<q[i]<<" ";
            }
            return ;
        }           
    for(int i=1;i<=n;i++)
    {
        if(b1[i]==0&&b2[x+i]==0&&b3[x-i+15]==0)
        {
            q[x]=i;
            b1[i]=1;b2[x+i]=1;b3[x-i+15]=1;
            dfs(x+1);
            b1[i]=0;b2[x+i]=0;b3[x-i+15]=0;
        }
    }
}
int main()
{
    //freopen("p1929.in","w",stdin);
    //freopen("p1929.out","r",stdout);
    cin>>n;
    dfs(1);
    cout<<ans;
    return 0;
}

by Xia3li @ 2023-10-14 22:04:42

修改点:\ 1.完成搜索后再输出;\ 2.每种方案输出后换行；\ 3.对于对角线上有无皇后判定条件改为x-i+n.

#include<bits/stdc++.h>
using namespace std;
int q[100],n,ans;
int b1[100],b2[100],b3[100];
void dfs(int x)
{
    if(x>n)
    {
        ans++;
        if(ans<=3)
        {
            for(int i=1;i<=n;i++)
                cout<<q[i]<<" ";
            cout<<endl;
            return ;
        }   
    }           
    for(int i=1;i<=n;i++)
    {
        if(b1[i]==0&&b2[x+i]==0&&b3[x-i+n]==0)
        {
            q[x]=i;
            b1[i]=1;b2[x+i]=1;b3[x-i+n]=1;
            dfs(x+1);
            b1[i]=0;b2[x+i]=0;b3[x-i+n]=0;
        }
    }
}
int main()
{
    //freopen("p1929.in","w",stdin);
    //freopen("p1929.out","r",stdout);
    cin>>n;
    dfs(1);
    cout<<ans;
    return 0;
}

AC记录

by 魏蕴博 @ 2023-10-14 22:14:06

@Xia3li AC了，谢谢 但n-i+15是对的 cout<<endl;要放在第一层for循环的外面