
计祘客-八皇后问题-https://nanti.jisuanke.com/t/381
发布日期:2022-02-08 04:20:46
浏览次数:1
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2023年09月06日 08时54分45秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
本地方法栈---JVM(六)
2019-03-07
执行引擎---JVM(十一)
2019-03-07
哈夫曼树及哈夫曼编码到底是怎么回事儿?
2019-03-07
KMP算法
2019-03-07
饿了么UI组件库中,Image组件预览图片错位的解决
2019-03-07
一个Scrapy项目实现同时爬取不同的网站,网站内不同的站点
2019-03-07
使用squoosh网的压缩方法实现浏览器前端压缩图片功能
2019-03-07
初探TypeScript
2019-03-07
ElementUI组件table展开expand子项动态获取数据时,视图不更新
2019-03-07
Canvas自定义文字旋转缩放渲染
2019-03-07
微信小程序中设置字体的坑
2019-03-07
Scrapy爬虫踩坑记录
2019-03-07
koa-body4接收formData数据
2019-03-07
koa返回前端响应后,后台静默做其他操作
2019-03-07
uniapp开发聊天APP踩坑记录
2019-03-07
JS实现网页开关灯效果
2019-03-07
前端实习笔试 亚信科技
2019-03-07
语言未动,博客先行
2019-03-07
printf函数使用—针对不同数据类型的输出结果详解
2019-03-07