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

3580 阅读 21 评论 0 点赞

本题与经典递归问题八皇后类似，只需要先放置完白皇后再放置黑皇后即可
解题思路:
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分

26 人评分

本文分类：题解列表
浏览次数：3580 次浏览
发布日期：2020-03-03 21:54:09
本文链接：https://blog.dotcpp.com/a/67415

上一篇 > 【蟠桃记】-题解(C语言代码)
下一篇 > string函数解决2070题-[STL训练]Mispelling4-题解(C++代码)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 21 条评论

斯宾塞 4年前回复TA

写的很详细 啊  谢谢大佬

正熠的伙伴 4年前回复TA

厉害

陈晨晨 4年前回复TA

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

恋爱的犀牛 4年前回复TA

详细

李华 4年前回复TA

@parkt90 @184231477 不能选的点，你是指矩阵当中是0的点吗？可以参考一下代码第36行，我判断了a[x][i]的值，如果它不为0才进行继续深搜，如果为0的话是不会进去搜索的，不会出现在里面死循环

parkt90 4年前回复TA

@parkt90 不好意思，大概明白了。

parkt90 4年前回复TA

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

小白 4年前回复TA

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

- 4年前回复TA

@- 了解 谢谢兄弟

李华 4年前回复TA

@- 防止特殊情况数组下标是负数，加个n就不会负数了，而且标记效果是一样的

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

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 21 条评论

发表评论 取消回复

评论列表共有 21 条评论

发表评论取消回复