李华

用户名：2645479600

访问量：17775

签　名：

等　　级
排　　名	470
经　　验	4582
参赛次数	2
文章发表	22
年　　龄	22
在职情况	学生
学　　校	华软、江理
专　　业	电信、计算机

　　自我简介：

欢迎探讨

TA的其他文章

蓝桥杯剪格子-题解(C语言代码)-----初学者可以看看，详细带图（dfs）
浏览：1067

[2013年第四届真题]危险系数-题解(C++代码)------STL，dfs
浏览：893

蓝桥杯历届试题-国王的烦恼-题解(C语言 with STL)---参考啊哈算法,文字解释详细
浏览：1413

你可能喜欢

蓝桥杯基础练习VIP-2n皇后问题-题解(C语言代码)--------详细带图解释皇后系列问题，适合新人

　　作者: 李华　　　　发表时间：2020-03-03 21:54:09 浏览：3400　|　评论：14　

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

本题与经典递归问题八皇后类似，只需要先放置完白皇后再放置黑皇后即可
解题思路:
1.先放置白皇后，再考虑第二个皇后
2.那么白皇后要怎么放呢，皇后不能同行同列，不能在同一条左斜线和右斜线。我们的递归函数是从第一行递归到最后一行，所以我们不需要标记行，那么我们拿三个数组分别标记列和两个斜线的占用情况。列的标记很容易理解，那么怎么标记左斜线和右斜线的占用情况呢？我们以左斜线为例子，请看图
![](/image_editor_upload/20200303092207_74969.png)
我们很容易可以发现黄线路径的每个格子行和列之和是相等的，比如（1,4）（2,3）的和都是5。同理观察一下红线，可以发现红线路径的格子行和列之和都为9。可以知道，左斜线的规律就是同一条斜线的格子，行列之和是相等的！

接下来请看右斜线：
![](/image_editor_upload/20200303092832_86855.png)
同样可以发现红线路径上的每个格子行和列之差是相等的，比如(1,1)(2,2)的差都是0。同理观察一下黄线，可以发现行列之差都是5。但是这里有一个坑点，请观察一下绿线，绿线路径的点行和列之差是-5，是一个负数，我们开数组的时候，下标不能为负数，这里我们只需要每次计算行列之差的时候，结果都给他加上一个n即可，下标就不可能出现负数了。比如（1,6）的差是-5，我们只需要在数组为（-5+8）=3的位置标记上就可以了。当然你不加n也可以，你可以加一个很大的数字也是同理（比如1000）的，但是这样的话你数组要开大一点。
##### 具体的标记数组命名可以看代码第四行，第五行。
3.我们先放白皇后，白皇后要考虑的总共有4个条件，列不能被占用，左斜线不能被白皇后占用，右斜线不能被占用，准备下的格子不能为‘0’。（行不能被占用不需要考虑，因为我们的递归函数是从第一行放到最后一行，不可能出现行重复）
##### 具体的判断代码可以看代码第三十六行
4.当白皇后完成了1~n行放置的一种情况，我们就可以开始尝试这种情况能不能完美放置黑皇后了。
##### 转入判断黑皇后的代码在第三十一行，子函数的参数是行数
5.接下来我们看判断黑皇后能不能完美放置。黑皇后要考虑的条件比白皇后条件多一个，有5个。首先列不能被同样的黑皇后占用，左斜线不能被占用，右斜线不能被占用，准备下的格子不能为‘0’，准备下的格子不能已经被白皇后占用。
##### 具体的判断代码可以看代码第十五行
6.当黑皇后考虑完了最后一行即已经完成了一种情况，让ans加一。

---
注意事项：当一种情况尝试到尽头也不能找到完美放置方法是要记得回溯，否则下次再想尝试这个格子就不能尝试了。所谓回溯，就是取消标记，避免下次递归无法尝试这个点。具体代码可以看第四十三行到第四十六行
**如果有不对的地方，请大佬指出。有疑问可以私信或者评论，谢谢！**
```c
#include <stdio.h>
int n,ans;
int a[10][10];	//棋盘
int vis_white_lie[10],vis_white_left[20],vis_white_right[20],white[10][10];	//用于标记白皇后的情况 
int vis_black_lie[10],vis_black_left[20],vis_black_right[20];
void dfs_black(int x)
{
	if(x==n+1)
	{
		ans++;
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis_black_lie[i]&&!vis_black_left[x+i]&&!vis_black_right[x-i+n]&&a[x][i]!=0&&white[x][i]==0)//列,左斜线,右斜线未占用，格子不为0，不被黑皇后占用 
		{
			vis_black_lie[i]=1;
			vis_black_left[x+i]=1;
			vis_black_right[x-i+n]=1;
			dfs_black(x+1);
			vis_black_lie[i]=0;	//回溯 
			vis_black_left[x+i]=0;
			vis_black_right[x-i+n]=0;	
		}
	}
}
void dfs_white(int x)	//先考虑白皇后,再考虑黑皇后，每完成一种情况就dfs_black递归找黑皇后的情况 
{
	if(x==n+1)	//白皇后已经完成了n行,准备进入第n+1行就算白皇后已经放完了
	{
		dfs_black(1);	//递归调用黑皇后 
		return;
	}
	for(int i=1;i<=n;i++)	//依次尝试1~n列
	{
		if(!vis_white_lie[i]&&!vis_white_left[x+i]&&!vis_white_right[x-i+n]&&a[x][i]!=0)	//如果列,左斜线,右斜线都没有被占用，并且格子不为0 
		{
			vis_white_lie[i]=1;
			vis_white_left[x+i]=1;	//左斜线x,y坐标相加相等
			vis_white_right[x-i+n]=1;	//右斜线,x,y坐标相减相等
			white[x][i]=1;	//将白皇后占的格子标记上,用于禁止黑皇后同时占用
			dfs_white(x+1);	//然后尝试第x+1行
			vis_white_lie[i]=0;
			vis_white_left[x+i]=0;
			vis_white_right[x-i+n]=0;
			white[x][i]=0;
		} 
	} 
} 
//从main函数看起 
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	dfs_white(1);	//参数代表当前考虑的行
	printf("%d",ans);
	return 0;
}
```

0.0分

45 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

代码纠错

SQL生成与解释

　　评论区

正熠的伙伴

厉害

2020-08-19 20:47:34

陈晨晨

写的很详细。。。。。。。

2020-07-16 05:07:25

恋爱的犀牛

详细

2020-03-26 02:53:26

parkt90

会不会在递归里面有死循环，比如输入的·矩阵很多点不能选，递归怎么跳出来？

2020-03-18 23:24:54

小白

写的很详细。b(￣▽￣)d

2020-03-16 21:46:25

为什么40行要写成x-i+n？

2020-03-03 22:09:58

李华

TA的其他文章

你可能喜欢

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

人民币问题（C语言代码）

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

【数组的距离】（C语言代码）

你的开发任务（C++代码）写到一半，等有心情回来补全

蓝桥杯基础练习VIP-2n皇后问题-题解(C语言代码)--------详细带图解释皇后系列问题，适合新人

评论区

精彩推荐

汽水瓶（C语言代码）怎么答案错误？？？？？

C语言训练-求素数问题（C语言代码）

WU-整数平均值（C++代码）

字符逆序（C语言代码）

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

愚蠢的摄影师（C++代码）

大神老白（C语言代码）

整数平均值（C语言代码）

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

回文数(一) （C语言代码）

李华

TA的其他文章

你可能喜欢

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

人民币问题 （C语言代码）

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

【数组的距离】 （C语言代码）

你的开发任务 （C++代码）写到一半，等有心情回来补全

蓝桥杯基础练习VIP-2n皇后问题-题解(C语言代码)--------详细带图解释皇后系列问题，适合新人

评论区

精彩推荐

汽水瓶 （C语言代码）怎么答案错误？？？？？

C语言训练-求素数问题 （C语言代码）

WU-整数平均值 （C++代码）

字符逆序 （C语言代码）

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

愚蠢的摄影师 （C++代码）

大神老白 （C语言代码）

整数平均值 （C语言代码）

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

回文数(一) （C语言代码）

人民币问题（C语言代码）

【数组的距离】（C语言代码）

你的开发任务（C++代码）写到一半，等有心情回来补全

　　评论区

汽水瓶（C语言代码）怎么答案错误？？？？？

C语言训练-求素数问题（C语言代码）

WU-整数平均值（C++代码）

字符逆序（C语言代码）

愚蠢的摄影师（C++代码）

大神老白（C语言代码）

整数平均值（C语言代码）