欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

蓝桥杯-基础训练-2n皇后问题

程序员文章站 2024-03-17 16:34:52
...

蓝桥杯-基础训练-2n皇后问题

首先是对于问题的分析

  • 之前有看到过关于八皇后的问题,但是没有去研究过怎么去解决这个问题。
    • 这次遇到之后,也比较棘手
  • 首先对于这个问题,我先是画了一下图,不难发现,每当我们放置一个皇后的时候,都需要去做一定的判断,而这次,即需要判断对角线,还有该行与该列。
  • 个人初期观点也没发现什么好用的技巧,就打算穷举了
  • 即穷举所有情况,但是发现就是原始的穷举,没有很好的方法去存储你每一步的结果,也就没有办法,在执行新的例子的时候,避开之前的结果
  • 所以就比较困惑,然后就去翻看了一下之前有关八皇后的问题,了解到了回溯对于本题的作用点
  • 一道经典的回溯算法题
  • 主要就是通过回溯去保存每步的结果,在得到可行解的时候,再去做新的试探。

实现时遇到的一些问题

  • 判断是否可插入的条件
    • 我第一判断对角线的时候写的 根据两坐标,各自的横纵坐标相减的绝对值做比较来判断是否在同一个对角线上。我初以为没问题,后来仔细看了一些,这样会多取一些点的
    • 后更改为根据两坐标,对应横纵坐标相减的绝对值是否相等来作为判断,就没有错误了
  • 而此题与八皇后问题不同的是
    • 此题可看多加了两次限制条件的 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;//同上,删除后,寻找是否还有新的可行解
			}
		}
	}
	

}

其他的题,也都有整理,可以看我的博客 断然不然嘞?