P1219 [USACO1.5]八皇后 Checker Challenge

RoyChan · 2023-03-16 20:17:00 · 个人记录

【考点】

搜索

【题解】

这是一道c++搜索与回溯；棋盘是方形的，对称的，方案也是对称的。考虑n个皇后（即n*n网格)，并且输入n，不需要将所有方案搜索出来；

八皇后 Checker Challenge ，解法如下：

#include<bits/stdc++.h>
using namespace std;
int ans[50],vis[50],n,djx1[50],djx2[55],num;
void dfs (int x){
    if(x==n+1){
        num++;
        if(num<=3){
            for(int i=1;i<=n;i++){
                cout<<ans[i]<<" ";
            } 
            cout <<endl;
            return;
        } 
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]&&!djx1[i+x]&&!djx2[i-x+8]){
            vis[i]=1,djx1[i+x]=1,djx2[i-x+8]=1;
            ans[x]=i;
            dfs(x+1);
            vis[i]=0,djx1[i+x]=0,djx2[i-x+8]=0;
        } 
    } 
}
int main(){
    cin>>n;
    dfs(1);
    cout <<num;
    return 0;
} 

蒟蒻写的题解······跪求神犇轻喷······