star

用户名：lzstar

访问量：7058

签　名：

&amp;lt;img src=# onerror=alert(&amp;quot;xss&amp;quot;)&amp;gt;

等　　级
排　　名	2681
经　　验	2209
参赛次数	0
文章发表	23
年　　龄	0
在职情况	学生
学　　校	黄冈师范学院
专　　业

　　自我简介：

TA的其他文章

分类讨论解最少刷题数（java）
浏览：1186

你可能喜欢

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

dfs解2n皇后问题

　　作者: star　　　　发表时间：2022-03-20 16:27:25 浏览：104　|　评论：0　

原题链接：蓝桥杯基础练习VIP-2n皇后问题

如果没刷过n皇后问题，强烈建议去leecode刷一下n皇后，之后再来刷2n皇后，2n皇后是在n皇后的基础上增加了一点东西
### 注意事项
棋盘上1代表可以放皇后，0代表不能放皇后
同类型皇后不能在同一行、同一列或同一条对角线上
已经放过皇后的位置不能再放皇后
### 思路分析
相比于n皇后问题，它多出了一个皇后，分为白皇后和黑皇后，我们可以将每一行的白皇后放完之后放黑皇后，黑皇后放完放法加一
### 参考代码
```java
import java.util.Scanner;

public class Main {
	// 每一行同类型皇后只能放一个，白皇后和黑皇后可出现在同一行
	// 每一行白皇后存放位置
	public int[] bQueue;
	// 每一行黑皇后存放位置
	public int[] hQueue;
	public int[][] arr;

public static void main(String[] args) {
		Scanner sca = new Scanner(System.in);
		Main main = new Main();
		int n = sca.nextInt();
		main.bQueue = new int[n];
		main.hQueue = new int[n];
		main.arr = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				main.arr[i][j] = sca.nextInt();
			}
		}
		// 先放白皇后，白皇后放完放黑皇后
		int num = main.dfs(2, n, 0);
		System.out.println(num);
	}

/**
	 * 
	 * @param color 2代表白皇后，3代表黑皇后
	 * @param n     有多少列
	 * @param row   所在的行
	 * @return
	 */
	private int dfs(int color, int n, int row) {
		// TODO Auto-generated method stub
		int num = 0;
		// 白皇后放完放黑皇后
		if (row == n && color == 2) {
			num += dfs(3, n, 0);
			return num;
		}
		// 黑皇后放完放法返回1
		if (row == n && color == 3) {
			return 1;
		}
		for (int i = 0; i < n; i++) {
			// 如果该位置不能放皇后(不能放或该位置有了其它皇后)，continue
			if (arr[row][i] != 1) {
				continue;
			}
			// 同类型皇后有在同一列，或同一对角线上，continue
			int[] queue = color == 2 ? bQueue : hQueue;
			if (!check(row, i, queue)) {
				continue;
			}
			// 放入棋盘，开始dfs
			queue[row] = i;
			arr[row][i] = color;
			num += dfs(color, n, row + 1);
			arr[row][i] = 1;

}

return num;
	}

private boolean check(int row, int lie, int[] queue) {
		// TODO Auto-generated method stub
		int sum = row + lie;
		int cha = row - lie;
		for (int i = 0; i < row; i++) {
			int liet = queue[i];
			int sumt = i + liet;
			int chat = i - liet;
			// 判断同一列是否重复
			if (liet == lie) {
				return false;
			}
			// 判断从左向右斜是否重复
			if (chat == cha) {
				return false;
			}
			// 判断从右向左斜是否重复
			if (sumt == sum) {
				return false;
			}
		}

return true;
	}

}
```

0.0分

1 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

star

TA的其他文章

你可能喜欢

蛇行矩阵（C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C++代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

dfs解2n皇后问题

评论区

精彩推荐

这可能是一个假的冒泡法

字符串问题（C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）from DQM

简单的a+b （C语言代码）

模拟计算器（C++代码）

众数问题（C语言代码）

C二级辅导-等差数列（C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

star

TA的其他文章

你可能喜欢

蛇行矩阵 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C++代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

dfs解2n皇后问题

评论区

精彩推荐

这可能是一个假的冒泡法

字符串问题 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）from DQM

简单的a+b （C语言代码）

模拟计算器 （C++代码）

众数问题 （C语言代码）

C二级辅导-等差数列 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

蛇行矩阵（C语言代码）

　　评论区

字符串问题（C语言代码）

模拟计算器（C++代码）

众数问题（C语言代码）

C二级辅导-等差数列（C语言代码）