当前位置:   article > 正文

DFS 典型题之 n 皇后(c++版)_n皇后问题c++ dfs

n皇后问题c++ dfs

n 皇后

前置知识:

根据数学函数 y = x +b;

当不同的一元函数的斜率相同时,唯一能区分他们的就是截距b

因此,可以由 b = y-x 得到不同的对角线直线函数(我们假设这些直线的斜率都是1)

那么反对角线 y = -x +b 所以b = x+y;

正对角线 b = y-x

可能出现b<0 的情况,所以我们给b加一个数当偏移量c,至于这个数是多少无所谓,只要保证这个数 c+y-x>0即可

其实b是多少不重要,重要的是我们能用b来唯一确定这条对角线,作为一个唯一表示,来映射出这条直线

优化版本:

整体思路:

全排列思想

因为每一行只能放一个皇后,只要当这一行出现过皇后,那就进入下一行

所以我们可以遍历每一行的所有列,只要在这个点放了皇后,那么直接进入下一行

#include<iostream>

int n;
char q[20][20];
bool f[100],zh[100],fn[100];

void dfs(int u){
    //已经遍历完了所有的行,输出答案
    if(u>n){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++)std::cout<<q[i][j];
            std::cout<<std::endl;
        }
        std::cout<<std::endl;
        return ;
    }
    
    for(int i=1;i<=n;i++){
        //f里面装的是这一列是否已经用过
        //有这三个判断在,只有满足题意的皇后能走到最后一层
        //不符合题意的提前剪枝了
        if(!f[i]&&!zh[i+u]&&!fn[n+u-i]){
            f[i] = zh[i+u] = fn[n+u-i] = true;
            q[u][i] = 'Q';
            dfs(u+1);//进入下一层
             f[i] = zh[i+u] = fn[n+u-i] = false;
             q[u][i] = '.';
        }
    }

}
int main(){

    std::cin>>n;

    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)q[i][j] = '.';
    dfs(1);
    return 0;

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41

原始暴力版

思路:

暴力遍历每一个格子是否能填皇后,所以有两种情况,填和不填

用数组剪枝一下,填的时候还要注意得能填,不能填的位置不能填,实现剪枝的效果

能填的情况:这一行,这一列,这一正对角线,这一反对角线都无皇后

#include<iostream>

const int N=100;
int n;
bool row[N],col[N],pl[N],inv[N];//行,列,正对角线,反对角线
char q[N][N];

void dfs(int x,int y,int num){ //num当前已经有多少八皇后存进去了
    if(y>n)y = 1,x++;
    if(x>n){
        if(num==n){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++)std::cout<<q[i][j];
                std::cout<<std::endl;
            }
            std::cout<<std::endl;
        }
        return ;
    }
    //不填八皇后
    dfs(x,y+1,num);
    if(!row[x]&&!col[y]&&!pl[x+y]&&!inv[n+y-x]){
        row[x] = col[y] = pl[x+y] = inv[n+y-x]  = true;
        q[x][y] = 'Q';
      
        //因为这一行填了皇后,进入下一行就要从第一列开始判断
        //num可以写在传参也可以写在外面
        //例如 num++;  dfs(x+1,1);num--;
        //记得恢复现场就行
        dfs(x+1,1,num+1);
        row[x] = col[y] = pl[x+y] = inv[n+y-x]  = false;
        q[x][y] = '.';
    }
}
int main(){
    std::cin>>n;
    for(int i=1;i<=n;i++)for(int j = 1;j<=n ;j++)q[i][j] = '.';
    dfs(1,1,0);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/825440
推荐阅读
相关标签
  

闽ICP备14008679号