一口气写完,自我感觉良好,不知道哪里错啦,求大佬指导

P1219 [USACO1.5] 八皇后 Checker Challenge

un_dauant @ 2023-02-17 17:26:24

#include<bits/stdc++.h>
#include <cstring>
#include <iomanip>
using namespace std;

const int N = 105;

int path[N];
//col[i] 表示该行该列 dg[i]表示 主对角线 , rdg[i]表示辅助对角线
bool col[N]={false} , dg[N]={false} ,rdg[N]= {false};

int n,cnt= 0; 

void dfs(int u){
    if(u == n){
        cnt++;
        if(cnt <=3){
            for(int i = 0 ;i< n;i++) cout << path[i] <<" ";
            cout << "\n";
        }
        return ;
    }
    //这里 i抽象为 列 ,u抽象为 行 分别对应  y = x+b y =-x+b (b= y-x +N (加上n之后同样也是唯一的) ) (b= y+x)
    for(int i = 1 ; i<=n;i++){   //从u行的第一列开始
        if(!col[i] && !dg[i+u] && !dg[n-i+u]){ // 剪枝
            path[u] = i;
            col[i] = dg[u+i] = rdg[n-i+u]  = true;
            dfs(u+1);
            col[i] = dg[u+i] = rdg[n-i+u]= false; // 回溯
        }
    }
}
int main()
{
    cin >> n;
    dfs(0);
    cout << cnt;
    return 0;

}

by un_dauant @ 2023-02-17 17:46:21

@un_dauant !dg[n-i+u] 应该改为 !rdg[n-i+u]

你 tmd 是真的菜


by fish_love_cat @ 2023-02-17 18:09:48

谔谔

我还以为是tlqtj


by guozhetao @ 2023-02-17 18:17:48

谔谔


|