李华

用户名：2645479600

访问量：13988

签　名：

等　　级
排　　名	401
经　　验	4128
参赛次数	2
文章发表	22
年　　龄	20
在职情况	学生
学　　校	华软
专　　业	电子信息工程

　　自我简介：

C/C++程序设计蓝桥杯新人，欢迎探讨

TA的其他文章

蓝桥杯算法提高VIP-3000米排名预测-题解(C++代码)---求出全部排列，逐个判断
浏览：431

蓝桥杯历届试题-最大子阵-题解(C语言代码)---dp最大子段和思想（详细）
浏览：1468

蓝桥杯2015年第六届真题-切开字符串（C++代码）---substr的简单枚举和map去重
浏览：573

你可能喜欢

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

　　作者: 李华　　　　发表时间：2020-03-03 21:54:09 浏览：2903　|　评论：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分

44 人评分

C语言网提供「C语言、C++、算法竞赛、真题百练、Python课程」在线课程，全部由资深研发工程师或ACM金牌大佬亲授课，更科学、全面的课程体系，以在线视频+在线评测的学习模式学习，学练同步，拒绝理论派，真正学会编程！还有奖学金等增值福利等你！

　　评论区

Yearn

大佬牛逼

2022-04-01 10:44:30 | |

jjdcxy

少了ans初始化为0

2022-02-17 12:30:44 | |

安逸

能详细说一下代码的执行顺序吗==

2021-12-06 09:10:09 | |

北叶南枫

很详细

2021-11-23 21:05:19 | |

北叶南枫

很详细

2021-11-23 21:04:48 | |

Crossing

很棒

2021-03-01 23:10:26 | |

小白

厉害

2020-09-17 20:33:19 | |

斯宾塞

写的很详细 啊  谢谢大佬

2020-09-17 09:44:08 | |

李华

TA的其他文章

你可能喜欢

母牛的故事（C语言代码）

文件的应用举例-应用fprintf函数

字符逆序（C语言代码）

单词个数统计（C++代码）

C二级辅导-分段函数（C语言代码）

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

评论区

精彩推荐

人见人爱A+B （C++代码）

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

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

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

蛇行矩阵（C语言代码）

矩形面积交（C语言代码）

小O的数字（C语言代码）

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

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

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）数组思路

李华

TA的其他文章

你可能喜欢

母牛的故事 （C语言代码）

文件的应用举例-应用fprintf函数

字符逆序 （C语言代码）

单词个数统计 （C++代码）

C二级辅导-分段函数 （C语言代码）

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

评论区

精彩推荐

人见人爱A+B （C++代码）

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

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

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

蛇行矩阵 （C语言代码）

矩形面积交 （C语言代码）

小O的数字 （C语言代码）

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

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

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）数组思路

母牛的故事（C语言代码）

字符逆序（C语言代码）

单词个数统计（C++代码）

C二级辅导-分段函数（C语言代码）

　　评论区

蛇行矩阵（C语言代码）

矩形面积交（C语言代码）

小O的数字（C语言代码）