解题思路:
这题可以直接暴力搜索出答案来，就是搜索的条件需要注意一下
解决方法： 深度优先搜索
用dfs一层一层搜索，先搜第0行，然后对第0行的每一列进行判断，如若可以落子，则落子，再考虑下一行，然后依旧对该行的每一列进行判断，以此类推；
如果无路可走了，就回溯
判断条件：
因为是 八皇后问题，所以就是 每个子的 行、列、两斜线 不能出现 棋子
所以，我们可以定义几个标记：
int vy[10], v1[20], v2[20];
vy[0] = 1 表示第 0 列 已经落了子了，则该列不能再放子了
v1[x + y ] = 1 表示 (x,y)这个点的 一条斜线已经落子了 (y = -x + b ， 所以在该斜线上 x + y 是定值)
同理 v2[x-y] = 1 表示(x,y)这个点的另一条斜线已经落子了 但是 x - y 可能是负值 ，所以最好加个 8 （因为极限情况是 x = 0 , y = 7 , 所以 0-7 = -7）
知道这些后就好判断了，看看代码吧！
参考代码:
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 | #include<stdio.h>#include<limits.h>int map[10][10];int vy[10], v1[20], v2[20];int ans = INT_MIN;//就是int的最小值。 头文件是<limits.h>//也可以 int ans = -10000; int check(int x, int y) { return !vy[y] && !v1[x + y] && !v2[x - y + 8];}void dfs(int row, int sum) { if (row == 8) { ans = ans > sum ? ans : sum; return; } for (int col = 0; col < 8; col++) { if (check(row, col)) { vy[col] = v1[row + col] = v2[row - col + 8] = 1; dfs(row + 1, sum + map[row][col]); vy[col] = v1[row + col] = v2[row - col + 8] = 0; } }}int main() { for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) scanf("%d", &map[i][j]); } dfs(0, 0); printf("%d\n", ans); return 0;} |
9.9 分
2 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复