首页 > 代码库 > 蓝桥杯 算法提高 8皇后·改 -- DFS 回溯
蓝桥杯 算法提高 8皇后·改 -- DFS 回溯
算法提高 8皇后·改
时间限制：1.0s 内存限制：256.0MB
问题描述
规则同8皇后问题，但是棋盘上每格都有一个数字，要求八皇后所在格子数字之和最大。
输入格式
一个8*8的棋盘。
输出格式
所能得到的最大数字和
样例输入
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 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
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 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
样例输出
260
数据规模和约定
棋盘上的数字范围0~99
关于八皇后问题（普通）:
http://blog.csdn.net/mbh_1991/article/details/23869459 这个博客写的十分的好，我学习八皇后问题也是参照了这篇博客。
关于本题：
1. 主要就是 用结构体 组织数据结构
const int maxn = 8;struct Map { int value; int row, col; //这里写完发现可以省略..... bool isQue; Map(int r = 0, int c = 0, int v = 0, bool Q = false) : row(r), col(c), value(v), isQue(Q) {}} map[maxn][maxn];2. 然后就如之前普通的八皇后解法差不多，在每到了一种方案，就对皇后标志为true的值统计一下sum, 对多种情况求max
#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>using namespace std;const int maxn = 8;struct Map { int value; int row, col; bool isQue; Map(int r = 0, int c = 0, int v = 0, bool Q = false) : row(r), col(c), value(v), isQue(Q) {}} map[maxn][maxn];//检测左上, 右上, 正上, 从上到下放置棋子, 且不需要检测横排 int dir[3][2] = {{-1, -1}, {-1, 1}, {-1, 0}};int Q_sum;int Q_max; //用不同方式摆放Que,和最大的是 int cnt;void init(); //初始化数据 bool check(int r, int c); //检测能否放皇后bool judge(int r, int c); //检测是否越界 void solve(); //解决问题的接口 void dfs(); //回溯,深搜void findMax(); //寻找方案的最大值 //启动程序 void AutoStartProcess();void init(){ for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) {// map[i][j].value = http://www.mamicode.com/i*8 + j + 1; >// map[i][j].isQue = false; cin >> map[i][j].value; map[i][j].isQue = false; map[i][j].row = i; map[i][j].col = j; } }}//检测越界, ture -- 没有越界 bool judge(int r, int c){ return (r >= 0 && r < maxn) && (c >= 0 && c < maxn);}//检测该位置是否能放皇后 bool check(int r, int c){ if (!judge(r, c)) return false; int p = 0; bool isOk = true; for (p = 0; p < 3; p++) //检测三个方向 { int tr = r, tc = c; //判断一个方向是否放过皇后 while (isOk && judge(tr, tc)) //判断是否越界 { tr = tr + dir[p][0]; tc = tc + dir[p][1]; //判断这个方向没有放过皇后 ，(!judge())越界当然是没有放过皇后的情况 isOk = isOk && (!judge(tr, tc) || !map[tr][tc].isQue); } } return isOk; //true-可以放皇后, 不可以返回false }void dfs(int cur){ int j = 0; if (cur == maxn) { //判断是否超过了第8-1行 findMax(); //计算当前方案的sum cnt++; } else { for (j = 0; j < maxn; j++) { if (check(cur, j)) { map[cur][j].isQue = true; dfs(cur + 1); map[cur][j].isQue = false; } } }}void findMax(){ for (int i_1 = 0; i_1 < maxn; i_1++) { for (int j_1 = 0; j_1 < maxn; j_1++) { if (map[i_1][j_1].isQue) { Q_sum += map[i_1][j_1].value; } } } if (Q_sum > Q_max) { Q_max = Q_sum; //更新最大值 } Q_sum = 0;}void solve(){ init(); dfs(0); printf("%d\n", Q_max);// cout << cnt << endl;}void AutoStartProcess(){ solve();}int main(){ AutoStartProcess(); return 0; }
蓝桥杯 算法提高 8皇后·改 -- DFS 回溯
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。