萌新刚学OI捞两次的八皇后求条

IaLWH @ 2024-08-09 13:28:41

#include<cstdio>
#define xrr x+j*dx[i]
#define yrr y+j*dy[i]
int n;
const int dx[8]={0,1,1,1,0,-1,-1,-1},dy[8]={1,1,0,-1,-1,-1,0,1};
int v[20][20];

int dfs(int x,int y){
    int ans=0;
    v[x][y]++;
    for(int i=0;i<8;i++)
        for(int j=1;xrr>=0&&xrr<n&&yrr>=0&&yrr<n;j++)
            v[xrr][yrr]++;

    for(int i=0;i<n;i++){
        if(x+1>=n)return 1;
        if(v[x+1][i])continue;
        ans+=dfs(x+1,i);
    }
    v[x][y]--;
    for(int i=0;i<8;i++)
        for(int j=1;xrr>=0&&xrr<n&&yrr>=0&&yrr<n;j++)
            v[xrr][yrr]--;
    return ans;
}
int main(){
    int n,ans=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        ans+=dfs(0,i);
    printf("%d",ans);
    return 0;
}

by haimingbei @ 2024-08-09 13:31:29

@IaLWH 简洁明了

#include<bits/stdc++.h>
using namespace std;
const int N=100;
int a[N],b[N],c[N],d[N],ans=0,n; //a[i]=j表示第i行皇后放在j列 
//b[j]表示j列有没有放了皇后，放了设为1，没有0. 
//c[i+j]能放设为0，放过了设为1；d[i-j+n]
void dfs(int i){//
    if(i==n+1){
        ans++;
        if(ans<=3){
            for(int j=1;j<=n;j++)cout<<a[j]<<" ";
            cout<<endl;
        }
        return ;
    }
    for(int j=1;j<=n;j++){
        if(!b[j] && !c[i+j] && !d[i-j+n]){
            a[i]=j;
            b[j]=1;
            c[i+j]=1;
            d[i-j+n]=1;
            dfs(i+1);
            b[j]=0;
            c[i+j]=0;
            d[i-j+n]=0;
        }
    }
} 
int main(){
    cin>>n;
    dfs(1);
    cout<<ans;
    return 0;
}

by IaLWH @ 2024-08-09 13:48:26

所以原代码哪里出了问题

by ZMQ_Ink6556 @ 2024-08-09 13:51:42

@IaLWH 简洁明了 2.0：

#include <bits/stdc++.h>
using namespace std;
const string ans[15] = {"" , "" , "" , "" , "" , "" , "2 4 6 1 3 5\n3 6 2 5 1 4\n4 1 5 2 6 3\n4" , "1 3 5 7 2 4 6\n1 4 7 3 6 2 5\n1 5 2 6 3 7 4\n40" , "1 5 8 6 3 7 2 4\n1 6 8 3 7 4 2 5\n1 7 4 6 8 2 5 3\n92" , "1 3 6 8 2 4 9 7 5\n1 3 7 2 8 5 9 4 6\n1 3 8 6 9 2 5 7 4\n352" , "1 3 6 8 10 5 9 2 4 7\n1 3 6 9 7 10 4 2 5 8\n1 3 6 9 7 10 4 2 8 5\n724" , "1 3 5 7 9 11 2 4 6 8 10\n1 3 6 9 2 8 11 4 7 5 10\n1 3 7 9 4 2 10 6 11 5 8\n2680" , "1 3 5 8 10 12 6 11 2 7 9 4\n1 3 5 10 8 11 2 12 6 9 7 4\n1 3 5 10 8 11 2 12 7 9 4 6\n14200" , "1 3 5 2 9 12 10 13 4 6 8 11 7\n1 3 5 7 9 11 13 2 4 6 8 10 12\n1 3 5 7 12 10 13 6 4 2 8 11 9\n73712"};
int n;
int main()
{
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    cout << ans[n];
    return 0;
}

by ZMQ_Ink6556 @ 2024-08-09 13:52:01

@IaLWH 这么做不如打表

by ZG10086 @ 2024-08-09 13:52:29

这题写回溯可能比较好