列公子

用户名：lielielie

访问量：10578

签　名：

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

　　自我简介：

TA的其他文章

1924题 - 01背包 - 动态规划 + 一维数组空间优化
浏览：535

你可能喜欢

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

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

　　作者: 列公子　　　　发表时间：2020-02-13 23:54:08 浏览：215　|　评论：0　

原题链接：蓝桥杯算法提高VIP-8皇后·改

# 2087题-[蓝桥杯][算法提高VIP]8皇后·改  DFS  (C++)

## 1. 算法

递归的深度优先搜索

## 2. 数据结构
```cpp
int place[maxn];	// 每一行的皇后在哪一列
bool isPlaced[maxn];	// 每一列是否已放置了皇后

int board[maxn][maxn];		// 棋盘
```

## 3. 完整代码 (AC)
```cpp
//
// 蓝桥杯题库 2087 8皇后·改
// 规则同8皇后，但棋盘上每格都有一个数字，要求八皇后所在格子数字之和最大
#include <cstdio>
#include <cmath>
const int maxn = 10;
const int N = 8;

int place[maxn];        // 每一行的皇后所在的列, 从 1 开始
bool isPlaced[maxn];    // 每一列是否有皇后

int board[maxn][maxn];      // 棋盘
int ans = -1, tmp = 0;		// 最优值, 临时值

void dfs(int row){
    if (row > N){
        if (tmp > ans)
            ans = tmp;
        return;
    }
    for (int col = 1; col < N+1; col++){
        if (!isPlaced[col]){
            // 检验对角线
            bool isSolution = true;
            for (int rr = 1; rr < row; rr++){
                if (abs(rr - row) == abs(place[rr] - col)){
                    isSolution = false;
                    break;
                }
            }
            if (isSolution){
                isPlaced[col] = true;
                place[row] = col;
                tmp += board[row][col];
                dfs(row + 1);
                tmp -= board[row][col];
                place[row] = 0;
                isPlaced[col] = false;
            }
        }
    }
}

int main(){
    for (int i = 1; i < 9; i++)
        for (int j = 1; j < 9; j++)
			scanf("%d", &board[i][j]);

dfs(1);
    printf("%d", ans);
    return 0;
}
```

0.0分

0 人评分

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

列公子

TA的其他文章

你可能喜欢

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

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

【绝对值排序】（C语言代码）

C二级辅导-公约公倍（C语言代码）

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

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

评论区

精彩推荐

C语言考试练习题_排列（C++代码）

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

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

C语言训练-素数问题（C语言代码）

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

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

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

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

1908题解

C语言训练-亲密数（C语言描述,反正怎么都能对）

列公子

TA的其他文章

你可能喜欢

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

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

【绝对值排序】 （C语言代码）

C二级辅导-公约公倍 （C语言代码）

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

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

评论区

精彩推荐

C语言考试练习题_排列 （C++代码）

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

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

C语言训练-素数问题 （C语言代码）

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

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

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

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

1908题解

C语言训练-亲密数 （C语言描述,反正怎么都能对）

【绝对值排序】（C语言代码）

C二级辅导-公约公倍（C语言代码）

　　评论区

C语言考试练习题_排列（C++代码）

C语言训练-素数问题（C语言代码）

C语言训练-亲密数（C语言描述,反正怎么都能对）