解题思路:
这题可以直接暴力搜索出答案来,就是搜索的条件需要注意一下
解决方法: 深度优先搜索
用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)
知道这些后就好判断了,看看代码吧!
参考代码:
#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; }
0.0分
3 人评分
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:541 |
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:538 |
十->二进制转换 (C语言代码)浏览:1291 |
printf基础练习2 (C语言代码)浏览:305 |
WU-图形输出 (C++代码)浏览:802 |
C语言程序设计教程(第三版)课后习题10.2 (C语言代码)浏览:510 |
母牛的故事 (C语言代码)浏览:716 |
1013题解浏览:561 |
C二级辅导-等差数列 (C语言代码)浏览:695 |
蛇行矩阵 (C语言代码)浏览:507 |