蓝桥杯vip试题 基础练习 2n皇后问题(java实现)

资源限制

时间限制:1.0s 内存限制:512.0MB

问题描述

  给定一个n*n的棋盘,棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后,使任意的两个黑皇后都不在同一行、同一列或同一条对角线上,任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法?n小于等于8。

输入格式

  输入的第一行为一个整数n,表示棋盘的大小。
  接下来n行,每行n个0或1的整数,如果一个整数为1,表示对应的位置可以放皇后,如果一个整数为0,表示对应的位置不可以放皇后。

输出格式

  输出一个整数,表示总共有多少种放法。

样例输入

4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

样例输出

2

样例输入

4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1

样例输出

0

我的分析:这里的2n皇后(黑白两个)和n皇后问题确实没太大区别,这里就从n皇后问题开始分析。这里它要求棋盘是随机地摆放0和1,所以还是得用个二维数组来表示棋盘,数组元素就存储0或1,黑或白。这个问题按经典算法分为两个部分,如何查找和如何判断。如何查找就是怎样遍历完整个棋盘,找到确定位置;如何判断就是怎样判断当前位置是“正确”的。

蓝桥杯vip试题 基础练习 2n皇后问题(java实现)

我们可以从第一个位置开始检索,从左到右,从上到下。因为要求不能在同一行,所以在当前行找到位置后就可以直接跳转到下一行 查找下一行的位置。因为每一行都是从第一个开始检索并且找到后就立即跳到下一行,所以不用判断同一行是否有相同皇后。我们只需要判断图中的三条红线,即列、左对角线和右对角线。又因为从左到右、从上到下的检索顺序,所以我们只用判断“前半部分”,后面的都还没有检索,所以肯定没有相同元素。如何判断就这样啦,接下来仔细思考如何查找。

用回溯的话,它是检索到了位置不对的地方,就马上回到上一行更变位置。比如我现在找到了第3行,但是每一列的位置都与上面摆好的位置冲突,我们这时就要回退到第2行,假设第2行第4列是之前摆好的,所以我们就是回退到(2,4),然后移到下一个位置也就是(2,5),不能往前移,因为前面的位置都是与上面的位置不符的,所以只能往后移,后面的都是没有检索过的位置。每次回退后,(2,4)这个原位置就要变回1,因为它已经不被我们所用,要及时变回原样。还有就是,当黑白皇后都摆好后,这时count++,函数也要回退,回退摆好的位置就会变为1,因为我们还要找新的摆放位置,所以这是必要的。我最开始还有个疑惑,黑的先还是白的先,黑白位置互换又是一种新的摆法,岂不是最后结果还要乘2?但是回溯的精妙之处解决了这些问题。回退是从后往前回退,第5行的所有可能找完后,它会回退到第4行,又换新的位置摆放,就这样它会回退到最初的第一行第一列这个位置,然后移到(1,2)这个又找新的摆放位置,这样的话,假设我们白的先,(1,1)刚才是被白的占了,现在白的移到(1,2),那么黑的就有机会移到(1,1)这个位置,所以我之前的顾虑黑白位置互换又乘2,是完全不用的。回溯法真的很暴力,它遍历了所有的可能性,以至于保证了我们结果的准确性。这里我们规定2表示白皇后,3表示黑皇后。

import java.util.Scanner;

public class Main {
	//用来存放棋盘
	static int[][] chessboard;
	//棋盘的“阶数”
	static int n;
	//皇后摆放的种类次数
	static int count;
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		chessboard = new int[n][n];
		for (int i = 0; i < n; i++) 
			for (int j = 0; j < n; j++) 
				chessboard[i][j] = in.nextInt();
		
		//默认从第0行开始,先找白皇后
		dfs(0, 2);
		System.out.println(count);
		in.close();
	}
	
	/**
	 * 判断当前位置是否能放
	 * @param x 行坐标
	 * @param y 列坐标
	 * @param type 是白是黑
	 * @return
	 */
	public static boolean check(int x, int y, int type) {
		if (chessboard[x][y] != 1) 
			return false;
		
		//判断当前列上是否有相同皇后
		for (int i = 0; i < x; i++) 
			if (chessboard[i][y] == type) 
				return false;
		
		//判断右对角线上是否有相同元素
		for (int i = x - 1, j = y + 1; i > -1 && j < n; i--, j++) 
			if (chessboard[i][j] == type) 
				return false;
			
		//判断左对角线上是否有相同元素
		for (int i = x - 1, j = y - 1; i > -1 && j > -1; i--, j--) 
			if (chessboard[i][j] == type) 
				return false;
			
		return true;
	}
	
	/**
	 * 摆放位置可以看作是找一条“通路”,当前位置不行就回退用dfs(回溯法)
	 * @param row 棋盘的行数
	 * @param type 2表示白皇后,3表示黑皇后
	 */
	public static void dfs(int row, int type) {
		//最后一行判断
		if (row == n) {
			if (type == 2) //如果白皇后确定好位置就开始摆黑皇后位置
				dfs(0, 3);
			else//若黑皇后摆好次数就加1
				count++;
			return;
		}
		//i表示列数,行数通过递归增长
		for (int i = 0; i < n; i++) 
			if (check(row, i, type)) {
				chessboard[row][i] = type;
				//这一行找好后就直接去下一行找
				dfs(row + 1, type);
				//找完回退到这里,这个位置就变成原样,为了找新的摆放位置
				chessboard[row][i] = 1;
			}
	}

}

上一篇:国产操作系统环境下VNC的使用教程


下一篇:oracle 11gR2 srvctl 命令启动数据库不成功处理总结