计祘客-八皇后问题-https://nanti.jisuanke.com/t/381
发布日期:2022-02-08 04:20:46
浏览次数:4
分类:技术文章
本文共 1041 字,大约阅读时间需要 3 分钟。
努比亚和苏丹没有子女,所以他要从一些有集成资格的继承者中挑选一个出来继承王位。他希望这个继承者足够聪明,所以他准备了一个西洋棋盘,上面的每个格子中均有一个 1-991−99 的数字。他又准备了 88 个皇后棋子。
88 皇后的规则就是不能有任何棋子同行或者同列或者同斜线,在满足这个规则的同时,王位继承者还需要让 88 个皇后所在的位置的数字的和是最大的。
用dfs 来实现
#includeusing namespace std;const int n = 8;int tmp, ans;int x[10];int chess[10][10];bool notDanger(int r, int c) {//判断是否存在相邻的皇后----函数, r 表示第几个皇后, c 表示是第几列 for (int i = 0; i < r; i++) { if (x[i] == c) return false; if (abs(r - i) == abs(c - x[i])) return false; } return true;}void queen(int k) {//放入第k行的皇后========感觉这个题用回溯和dfs 是一样的,没看出来有什么区别 if (k == n) { ans = max(ans, tmp); return; }//所有行都尝试完毕,即求出了相应一组解 for (int i = 0; i < n; i++) { if (notDanger(k, i)) {//没有冲突,尝试下一行 x[k] = i; tmp += chess[k][i];//计算他的坐标值进行相加 queen(k + 1); x[k] = -1;//注意下层递归结束后及时更新相应变量值************* tmp -= chess[k][i]; } }}int main() { int t; scanf("%d", &t); while (t--) { tmp = ans = 0; memset(x, -1, sizeof(x)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) scanf("%d", &chess[i][j]); } queen(0); printf("%d\n", ans); } return 0;}
转载地址:https://blog.csdn.net/weixin_38960774/article/details/79395855 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
初次前来,多多关照!
[***.217.46.12]2024年03月20日 12时45分58秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
SpringBoot 集成webSocket 打成jar包ba
2021-06-28
富文本编辑的内容导出为word
2021-06-28
字节跳动:估值迷雾下各自的小九九
2021-06-28
sql注入
2021-06-28
textarea在光标后追加内容,并将换行符替换成br标签
2021-06-28
kafka客户端脚本windows版
2021-06-28
zookeeper基础教程
2021-06-28
zookeeper单机版安装教程
2021-06-28
zookeeper集群版安装教程
2021-06-28
Spring @Cacheable当返回值为null时报错解决方案
2021-06-28
小数在计算机中如何存储?
2021-06-28
什么是二分查找、插值查找、斐波那契查找和索引查找?
2021-06-28
什么是二叉查找树,有什么优势?
2021-06-28
教你玩转二叉查找树的结点插入和删除操作
2021-06-28
下次再让你讲平衡二叉树,可别说不会了
2021-06-28
什么是B-树、B树、B+树、B*树?
2021-06-28
B树结点的插入删除操作
2021-06-28
String s=new String(“abc“)创建了几个对象?
2021-06-28
【干货】Linux 网卡绑定的相关知识和技巧
2021-06-28
学习笔记2021-01-13
2021-06-28