计祘客-八皇后问题-https://nanti.jisuanke.com/t/381
发布日期:2022-02-08 04:20:46 浏览次数:1 分类:技术文章

本文共 1041 字,大约阅读时间需要 3 分钟。

努比亚和苏丹没有子女,所以他要从一些有集成资格的继承者中挑选一个出来继承王位。他希望这个继承者足够聪明,所以他准备了一个西洋棋盘,上面的每个格子中均有一个 1-99199 的数字。他又准备了 88 个皇后棋子。

88 皇后的规则就是不能有任何棋子同行或者同列或者同斜线,在满足这个规则的同时,王位继承者还需要让 88 个皇后所在的位置的数字的和是最大的。

用dfs 来实现

#include
using 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:hd2298
下一篇:==和equals的区别和联系

发表评论

最新留言

网站不错 人气很旺了 加油
[***.192.178.218]2023年09月06日 08时54分45秒