网课：N皇后问题——牛客（题解和疑问）

题目描述

给出一个n×nn\times nn×n的国际象棋棋盘，你需要在棋盘中摆放nnn个皇后，使得任意两个皇后之间不能互相攻击。具体来说，不能存在两个皇后位于同一行、同一列，或者同一对角线。请问共有多少种摆放方式满足条件。

输入描述:

一行，一个整数n(1≤n≤12)n(1\le n \le 12)n(1≤n≤12)，表示棋盘的大小。

输出描述:

输出一行一个整数，表示总共有多少种摆放皇后的方案，使得它们两两不能互相攻击。

示例1

输入

4

输出

2

想法：

就按题意，一个格子一个格子枚举，并看一下有没有行冲突，列冲突，对角线冲突，但结果答案是错的。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int ans=0;
int a[15][15];
int st[15][15];
int r[15];//行冲突
int c[15];//列冲突
int djx[2];//对角线冲突
void dfs(int gs){//摆了的皇后个数
    //st[x][y]=1;
    if(gs>n){
        ans++;
        return ;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            //if(st[i][j]) break;
            if(r[i]) break;
            if(c[j]) continue;
            if(djx[0]&&i==j) continue;
            if(djx[1]&&i+j==n+1) continue;
            r[i]=1;
            c[j]=1;
            if(i==j){
                djx[0]=1;
                dfs(gs+1);
                djx[0]=0;
            }
            else if(i+j==n+1){
                djx[1]=1;
                dfs(gs+1);
                djx[1]=0;
            }
            else dfs(gs+1);
            r[i]=0;
            c[j]=0;
        }
    }
}
int main(){
    cin>>n;
    dfs(0);
        cout<<ans;
}

网课：

看了网课后，发现还是有点问题的吧。首先，对角线冲突理解错了，题目指的是每条对角线，而我以为是主对角线和副对角线两条。然后我又想了下怎么标记对角线，找了下对角线的下标有什么规律，emm但也还是想不到怎么表示。网课的提供了两种方法，一种是直接将所有对角线标序号，然后弄个标记数组；第二种就是看规律，主对角线方向上的位于同一条对角线的坐标i+j都是同一个值，副对角线方向上的位于同一条对角线的坐标i-j都是同一个值。利用这点，可以弄两个标记数组。但还有问题，就是副对角线方向上的某些对角线坐标相减是负的，需要把数组下标平移一下。我找规律的时候也有注意到一点点吧，但没那么深刻。还有一点，就是网课的方法搜索时是一行一行搜的，每一行放一个皇后，看是否满足条件，这样直接不用考虑行冲突了。我是一格一格搜索的，复杂度更高。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=15;
int n;
int ans=0;
int c[N];
int fdjx[N+N-1+N];//平移
int zdjx[N+N-1];
void dfs(int r){//行
    if(r>n){
        ans++;
        return ;
    }
    for(int i=1;i<=n;i++){//列
        if(c[i]) continue;
        if(fdjx[r-i+n]) continue;
        if(zdjx[r+i]) continue;
        c[i]=1;
        fdjx[r-i+n]=1;
        zdjx[r+i]=1;
        dfs(r+1);
        c[i]=0;
        fdjx[r-i+n]=0;
        zdjx[r+i]=0;
    }
}
int main(){
    cin>>n;
    dfs(1);
    cout<<ans;
}

修改：

但是吧，我现在按我的想法写，就是一格一格搜索，还是弄不出来。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=15;
int n;
int ans=0;
int c[N];
int r[N];
int fdjx[N+N-1+N];//平移
int zdjx[N+N-1];
void dfs(int gs){//行
    if(gs>n){
        ans++;
        return ;
    }
    for(int i=1;i<=n;i++){//列
        for(int j=1;j<=n;j++){
            if(c[j]) continue;
            if(r[i]) break;
            if(fdjx[i-j+n]) continue;
            if(zdjx[i+j]) continue;
            c[j]=1;
            r[i]=1;
            fdjx[i-j+n]=1;
            zdjx[j+i]=1;
            dfs(gs+1);
            c[i]=0;
            r[i]=0;
            fdjx[i-j+n]=0;
            zdjx[j+i]=0;
        }  
    }
}
int main(){
    cin>>n;
    dfs(1);
    cout<<ans;
}