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

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

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

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