流离之人追逐幻影

用户名：pwj666

访问量：60203

签　名：

不想总是要失去后才懂得珍惜

等　　级
排　　名	37
经　　验	13954
参赛次数	11
文章发表	110
年　　龄	23
在职情况	在职
学　　校
专　　业

　　自我简介：

TA的其他文章

【原理、题解、代码】最大公约数与最小公倍数
浏览：186

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(1) （C++代码）

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

优质题解

蓝桥杯基础练习VIP-2n皇后问题（递归回溯）-题解

　　作者: 流离之人追逐幻影　　　　发表时间：2019-07-17 17:36:17 浏览：1251　|　评论：0　

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

这是n皇后问题的升级版，所以要AC这道题必须得学会n皇后递归或者是非递归的解题方法。解决了2n皇后问题，多n皇后也是一样可以解决的。需要了解n皇后，可以参考一下我做的笔记^_^.
[n皇后（递归回溯）-----每日PAT](https://blog.dotcpp.com/a/60769 "n皇后（递归回溯）-----每日PAT")
[n皇后（非递归回溯）-----每日PAT](https://blog.dotcpp.com/a/60771 "n皇后（非递归回溯）-----每日PAT")

大致思路：
```
2n皇后其实就是先计算第一个n皇后，然后得出来一个n皇后的表，之后在计算另一个n皇后，这个时候第二种n皇后的情况就要除去第一种n皇后已经放入的位置。
```
大致实现：
```
在n皇后的基础上+题意，用一个二维数组chessboard[][]，代表该位置是否可以放置皇后，用一个数组bqueen[]来放置黑皇后，用一个数组wqueen[]来放置白皇后。
从主程序开始，先放一组白皇后，放完之后再继续置一组黑皇后。
```
```
需要注意的有两点，
1.递归部分：白皇后只需用chessboard[][]来判断是否进行下一步递归，黑皇后需要用wqueen[]和chessboard[][]来判断是否进行下一步递归;
2.递归终止：说明一组皇后放置完成.白皇后需要开始黑皇后的放置,黑皇后需要进行计数。
```

```
#include<stdio.h>
#include<string.h>
#include<math.h>

#define MAXSIZE 1000
int bqueen[MAXSIZE];//黑皇后
int wqueen[MAXSIZE];//白皇后
int chessboard[MAXSIZE][MAXSIZE];//1:能放  0:不能放
int count =0;
int n;

int BlackQueen(int k)

{
	int i;	
	int j;

for(i =0; i < k -1; i++){	
		int judge = bqueen[i]- bqueen[k -1];
		if(judge ==0|| fabs(k -1- i)== fabs(judge))	
			return 0;
	}

if(k == n)	{//计数
		count++;
		return 0;	
	}

for( j =0; j < n; j++)	{
		if(j != wqueen[k]&& chessboard[k][j])	{
		//该位置可以放置且没有放置白皇后
			bqueen[k]= j;
			BlackQueen(k +1);	
		}	
	}
	
	
}

int WhiteQueen(int k){
	int i;
	int j;
	for( i =0; i < k -1; i++)	{ 
	//判断当前放置的皇后与之前的是否冲突
		int judge = wqueen[i]- wqueen[k -1];	
		if(judge ==0|| fabs(k -1- i)== fabs(judge))	
			return 0;
	}

if(k == n)	{ //放置完一组白皇后，则开始从第一行放置黑皇后
		BlackQueen(0);
		return 0;	
	}

for( j =0; j < n; j++)	{//白皇后递归
		if(chessboard[k][j])	{	//该位置可以放置
			wqueen[k]= j;	
			WhiteQueen(k +1);	//下一步递归
		}	
	}
	
	
}
int main(void){  
	int i;
	int j;
	scanf("%d",&n);
	for(i =0; i < n; i++)
		for(j =0; j < n; j++)
			scanf("%d",&chessboard[i][j]);
	WhiteQueen(0);//从第一行开始放置皇后
	printf("%d\n",count);
	return 0;
}

```

0.0分

6 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

流离之人追逐幻影

TA的其他文章

你可能喜欢

C二级辅导-计负均正（C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C++代码）

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

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

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

蓝桥杯基础练习VIP-2n皇后问题（递归回溯）-题解

评论区

精彩推荐

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

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

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

C语言训练-立方和不等式（C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

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

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

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

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

字符逆序（C语言代码）

流离之人追逐幻影

TA的其他文章

你可能喜欢

C二级辅导-计负均正 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C++代码）

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

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

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

蓝桥杯基础练习VIP-2n皇后问题（递归回溯）-题解

评论区

精彩推荐

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

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

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

C语言训练-立方和不等式 （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

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

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

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

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

字符逆序 （C语言代码）

C二级辅导-计负均正（C语言代码）

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

　　评论区

C语言训练-立方和不等式（C语言代码）

字符逆序（C语言代码）