一个人的巴黎

用户名：uq_36478041918

访问量：14979

签　名：

等　　级
排　　名	105
经　　验	8303
参赛次数	1
文章发表	70
年　　龄	0
在职情况	学生
学　　校	NTU
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

蓝桥杯2017年第八届真题-日期问题
浏览：170

蓝桥杯2017年第八届真题-k倍区间【前缀和+数学优化】
浏览：241

蓝桥杯2018年第九届真题-耐摔指数
浏览：346

你可能喜欢

蓝桥杯基础练习VIP-2n皇后问题

　　作者: 一个人的巴黎　　　　发表时间：2022-03-10 00:36:07 浏览：624　|　评论：0　

原题链接：蓝桥杯基础练习VIP-2n皇后问题

**2n皇后问题分析**:
与n皇后思路大体相同，首先搜索黑(或白)皇后的位置，每确定一次黑(或白)皇后的位置，搜索另一色皇后的位置，即两次搜索，如果可以找到结果，则cnt++，下文代码中用**visBlack[][]**和**visWhite[][]**记录黑白皇后分别有没有在该位置。注意在搜索白皇后(或黑皇后)时要注意判断此位置是否已经放置另一色皇后，若已放置**（visBlack[row][col]==1）或者visWhite[row][col]==1）**则直接跳过当前情况。

```cpp
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int map[8][8];//1表示是否可以放置皇后，0表示不能
int visBlack[8][8];//记录黑皇后有没有在该位置
int visWhite[8][8];//记录白皇后有没有在该位置
int cnt=0;//计数
bool checkBlack(int row,int col){
    for(int i=0;i<n;i++){//检查行是否与列冲突
        if(visBlack[i][col]==1)  return false;
    }
     //只检查左对角线上方，因为下方还没有访问
    for(int j=row-1,k=col-1;j>=0&&k>=0;j--,k--){//检查左对角线
        if(visBlack[j][k]==1)  return false;
    }
     //只检查左对角线上方，因为下方还没有访问
    for(int j=row-1,k=col+1;j>=0&&k<n;j--,k++){//检查右对角线
        if(visBlack[j][k]==1)  return false;
    }
    return true;
}
//同理
bool checkWhite(int row,int col){
    for(int i=0;i<n;i++){
        if(visWhite[i][col]==1)  return false;
    }
    
    for(int j=row-1,k=col-1;j>=0&&k>=0;j--,k--){
        if(visWhite[j][k]==1)  return false;
    }
    
    for(int j=row-1,k=col+1;j>=0&&k<n;j--,k++){
        if(visWhite[j][k]==1)  return false;
    }
    return true;
}
//按行寻找白皇后节点，此函数在黑皇后满足的条件下才执行
void dfsWhite(int row){
    if(row==n){
        cnt++;
        return;
    }
    
    for(int col=0;col<n;col++){
        if(map[row][col]==0||visBlack[row][col]==1)//不能放置或者放置过黑皇后  直接跳过  
            continue;
        if(checkWhite(row,col)){//检查皇后摆放是否合适
            visWhite[row][col]=1;//标记该位置已经摆放过白皇后
            dfsWhite(row+1);
            visWhite[row][col]=0;//回溯
        }
        
    }
}
//按行寻找黑皇后节点
void dfsBlack(int row){
    if(row==n){
        dfsWhite(0);
        return;
    }
    
    for(int col=0;col<n;col++){
        if(map[row][col]==0)//不能放置直接跳过
            continue;
        if(checkBlack(row,col)){//检查皇后摆放是否合适
            visBlack[row][col]=1;//标记该位置已经摆放过黑皇后
            dfsBlack(row+1);
            visBlack[row][col]=0;//回溯
        }
        
    }
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>map[i][j];
        }
    }
    dfsBlack(0);
    cout<<cnt<<endl;
    return 0;
}
```

0.0分

4 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

一个人的巴黎

TA的其他文章

你可能喜欢

人见人爱A+B （C++代码）

【计算两点间的距离】（C语言代码）

C语言训练-谁家孩子跑最慢* （C语言代码）

简单的a+b （C语言代码）

DNA （C语言描述，数据结构）

蓝桥杯基础练习VIP-2n皇后问题

评论区

精彩推荐

母牛的故事（C语言代码）

最好的，

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

1231题解(注意理解“输入多个测试实例”)

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

ACM俱乐部密码

数字统计（C语言代码）

A+B for Input-Output Practice (I) （C语言代码）

一个人的巴黎

TA的其他文章

你可能喜欢

人见人爱A+B （C++代码）

【计算两点间的距离】 （C语言代码）

C语言训练-谁家孩子跑最慢* （C语言代码）

简单的a+b （C语言代码）

DNA （C语言描述，数据结构）

蓝桥杯基础练习VIP-2n皇后问题

评论区

精彩推荐

母牛的故事 （C语言代码）

最好的，

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

1231题解(注意理解“输入多个测试实例”)

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

ACM俱乐部密码

数字统计 （C语言代码）

A+B for Input-Output Practice (I) （C语言代码）

【计算两点间的距离】（C语言代码）

　　评论区

母牛的故事（C语言代码）

数字统计（C语言代码）