蓝桥杯-基础训练-2n皇后问题
程序员文章站
2024-03-17 16:34:52
...
首先是对于问题的分析
- 之前有看到过关于八皇后的问题,但是没有去研究过怎么去解决这个问题。
- 这次遇到之后,也比较棘手
- 首先对于这个问题,我先是画了一下图,不难发现,每当我们放置一个皇后的时候,都需要去做一定的判断,而这次,即需要判断对角线,还有该行与该列。
- 个人初期观点也没发现什么好用的技巧,就打算穷举了
- 即穷举所有情况,但是发现就是原始的穷举,没有很好的方法去存储你每一步的结果,也就没有办法,在执行新的例子的时候,避开之前的结果
- 所以就比较困惑,然后就去翻看了一下之前有关八皇后的问题,了解到了回溯对于本题的作用点
- 一道经典的回溯算法题
- 主要就是通过回溯去保存每步的结果,在得到可行解的时候,再去做新的试探。
实现时遇到的一些问题
- 判断是否可插入的条件
- 我第一判断对角线的时候写的 根据两坐标,各自的横纵坐标相减的绝对值做比较来判断是否在同一个对角线上。我初以为没问题,后来仔细看了一些,这样会多取一些点的
- 后更改为根据两坐标,对应横纵坐标相减的绝对值是否相等来作为判断,就没有错误了
- 而此题与八皇后问题不同的是
- 此题可看多加了两次限制条件的 n皇后问题
- 即第一个限制条件是0,第二个显示条件是黑红限制,即已经放置了皇后的点,自然也就不能再放置了
- 故我们可以在第一个限制的基础上做第二个,即可。
- 这里要说一下的是,黑红是对等的,不分先后顺序的。故不用考虑太多。
import java.util.Arrays;
import java.util.Scanner;
public class Main {
private static int count = 0 ;// 即最终结果
private static int step = 0; // 即步长,即现已经放入的皇后个数
private final static int RED = 2; // 红皇后
private final static int BLACK = 3; // 黑皇后
private static int Queens = 0; // 皇后个数
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int c = sc.nextInt();
int[][] a = new int[c][c];
Queens = 2*c;
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a.length; j++) {
a[i][j] = sc.nextInt();
}
}
hs(a, 0, 0, RED);
System.out.println(count);
}
/**
*
* @Description 判断是否在该位置是否可以填入皇后
* @author duanran
* @date 2020-3-21下午09:33:01
* @param a 棋盘
* @param i 横坐标
* @param j 纵坐标
* @param colour 红/黑皇后
* @return 是否可以插入
*/
public static boolean canIn(int[][] a,int i,int j,int colour) {
for (int j2 = 0; j2 < a.length; j2++) {
for (int k = 0; k < a[j2].length; k++) {
// 判断是否是其攻击目标,即该列,该行,对角线
if (j2==i||k==j||Math.abs(i-j2)==Math.abs(k-j)) {
// 与之不同的是,看此元素是否已被占用,即是否为0或者是否为其他皇后
if (a[j2][k]==colour||a[i][j]!=1) {
return false;
}
}
}
}
return true;
}
/**
*
* @Description 回溯法,用于迭代遍历棋盘
* @author duanran
* @date 2020-3-21下午09:34:14
* @param a 棋盘
* @param i 横坐标
* @param j 纵坐标
* @param colour 红/黑皇后
*/
public static void hs(int[][] a,int i,int j,int colour){
// 判断是否已经填满了足够的皇后
if (step==Queens) {
count++;
return;
}
// 判断是否已经放置满了红/黑皇后
if (step==Queens/2) {
//即从已经放置红皇后的棋盘上,从头开始放置黑皇后
i=j=0;
colour=BLACK;
}
for (int k = j; k < Queens/2; k++) {
if (canIn(a, i, k, colour)) { // 判断是否可以放入皇后
a[i][k] = colour; // 放入皇后
++step; // 步长加1
hs(a, i+1, 0, colour); // 进行下一行的皇后放置
a[i][k] = 1; // 删除已捕获,结果,
--step;//同上,删除后,寻找是否还有新的可行解
}
}
}
}
其他的题,也都有整理,可以看我的博客 断然不然嘞?
上一篇: python基础day04
下一篇: Python基础——day04