DFS 超时求调

P1219 [USACO1.5] 八皇后 Checker Challenge

2010Song @ 2024-08-07 19:19:03

#include<bits/stdc++.h>
using namespace std;
int n,ans;
bool b[15][15],c[15];
void print(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(b[i][j]==1){
                cout<<j<<" ";
            }
        }
    }
    cout<<endl;
}
bool check(int x,int y){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(b[i][j]){
                if(i-j==x-y||i+j==x+y){
                    return 0;
                }
            }
        }
    }
    return 1;
}
void dfs(int k){//k是行 

    if(k==n+1){
        ans++;
        if(ans<=3){
            print();
        }
        return;
    }
    for(int i=1;i<=n;i++){
        if(!c[i]&&check(k,i)){
        c[i]=1;
        b[k][i]=1;
        dfs(k+1);
        b[k][i]=0;  
        c[i]=0;
        }
    }
}
int main(){
    cin>>n;
    dfs(1);
    cout<<ans;
    return 0;
}

by Night_sea_64 @ 2024-08-07 19:35:42

@2010Song

check() 太慢了。您直接记录每列是否占了、每条对角线是否占了就好了啊


by 2010Song @ 2024-08-08 18:44:40

感谢大佬(已关注您)


|