列公子

用户名：lielielie

访问量：10578

签　名：

等　　级
排　　名	1691
经　　验	2704
参赛次数	0
文章发表	20
年　　龄	0
在职情况	学生
学　　校	哈尔滨工程大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高-学霸的迷宫 BFS- (C++)
浏览：635

蓝桥杯算法提高VIP-8皇后·改 DFS (C++)
浏览：215

蓝桥杯基础练习- 2n皇后问题 DFS (C++代码)
浏览：273

你可能喜欢

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

蓝桥杯基础练习- 2n皇后问题 DFS (C++代码)

　　作者: 列公子　　　　发表时间：2020-02-15 19:51:18 浏览：273　|　评论：0　

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

# 2n 皇后问题 DFS
```cpp
//
// Created by LiuLu on 2020/2/15.
// 2n 皇后
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 10;
int N;
// 是否可以放
bool isAble[maxn][maxn];

int placeW[maxn];   // 每一行中, 白皇后所在的列数, 0 为未放
int placeB[maxn];   // 每一行中, 黑皇后所在的列数

bool isPlacedW[maxn];   // 第 i 列是否放了白皇后
bool isPlacedB[maxn];   // 第 i 列是否放了黑皇后

int dfsBlack(int row){      // 放置黑皇后
    if (row == N + 1){
        return 1;
    }
    int ans = 0;
    for (int col = 1; col <= N; col++){
        if (!isPlacedB[col] && isAble[row][col] && placeW[row] != col){
            // 检查对角线
            bool isSolution = true;
            for (int rr = 1; rr < row; rr++){
                if (abs(rr - row) == abs(col - placeB[rr])){
                    isSolution = false;
                    break;
                }
            }
            if (isSolution) {
                placeB[row] = col;
                isPlacedB[col] = true;
                ans += dfsBlack(row + 1);
                isPlacedB[col] = false;
                placeB[row] = 0;
            }
        }
    }
    return ans;
}

int dfsWhite(int row){
    if (row == N + 1){
        // 开始放黑皇后
        memset(isPlacedB, 0, sizeof(isPlacedB));
        return dfsBlack(1);
    }
    int ans = 0;
    // 遍历每一列
    for (int col = 1; col <= N; col++){
        if (!isPlacedW[col] && isAble[row][col]){
            // 检查对角线
            bool isSolution = true;
            for (int rr = 1; rr < row; rr++){
                if (abs(rr - row) == abs(col - placeW[rr])){
                    isSolution = false;
                    break;
                }
            }
            if (isSolution) {
                placeW[row] = col;
                isPlacedW[col] = true;
                ans += dfsWhite(row + 1);
                isPlacedW[col] = false;
                placeW[row] = 0;
            }
        }
    }
    return ans;
}

int main(){
    scanf("%d", &N);
    int aa;
    for (int i = 1; i < N + 1; i++)
        for (int j = 1; j < N + 1; j++){
            scanf("%d", &aa);
            isAble[i][j] = (bool) aa;
        }

int ans = dfsWhite(1);
    printf("%d", ans);
    return 0;
}

```

0.0分

1 人评分

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

列公子

TA的其他文章

你可能喜欢

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

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

单词个数统计（C++代码）

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

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

蓝桥杯基础练习- 2n皇后问题 DFS (C++代码)

评论区

精彩推荐

计算质因子（C++代码）100以内质数直接打表就好了

三进制小数（C语言代码）

C二级辅导-同因查找（C语言代码）

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

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

WU-输出九九乘法表（C++代码）

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

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

愚蠢的摄影师（C++代码）

列公子

TA的其他文章

你可能喜欢

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

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

单词个数统计 （C++代码）

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

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

蓝桥杯基础练习- 2n皇后问题 DFS (C++代码)

评论区

精彩推荐

计算质因子 （C++代码）100以内质数直接打表就好了

三进制小数 （C语言代码）

C二级辅导-同因查找 （C语言代码）

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

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

WU-输出九九乘法表 （C++代码）

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

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

愚蠢的摄影师 （C++代码）

单词个数统计（C++代码）

　　评论区

计算质因子（C++代码）100以内质数直接打表就好了

三进制小数（C语言代码）

C二级辅导-同因查找（C语言代码）

WU-输出九九乘法表（C++代码）

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

愚蠢的摄影师（C++代码）