C语言网奉行“学练同步，知行合一”的学习理念，希望大家都能理论与动手一起加强！拒绝理论派！
每月月赛，最后一个周六晚八点开始，请提前预约参赛，参与排名！
混一天和努力一天，一天看不出任何差别，三天看不到任何变化，七天也看不到任何距离……
但是一个月后会看到话题不同，三个月后会看到气场不同，半年后会看到距离不同，一年后会看到人生道路截然不同。
请坚信你所喜爱的事物！
通知：举办比赛权限已经完全开放，支持老师、个人随时抽题创建校内赛等比赛，达到P2级即可
因比赛为公共资源，比赛名称建议包含学校/组织名称具有辨识度，比赛名称、公告不文雅、灌水将被删除比赛并取消权限！
题库的题不仅仅支持C语言C++、java，Python和php也可以提交
编程小组功能上线！欢迎各位老师、社团协会小组负责人申请创建，方便教学、训练！
申请优质题解的标准第一，代码格式工整整齐，第二，不少于300字的思路讲解，有配图更佳！
代码格式工整、有详细说明和配图的题解才有更多的浏览哦
学习交流 QQ1群156740915、4群 364137421、 211300176、博主群487133400 Python小组群 783851273 验证信息备注网站昵称！
个人资料中有关于自己联系地址、联系电话的信息，用于我们邮寄奖品福利等，且信息不会公开，别人看不到，请大家知晓！
注意，恶意创建比赛、直接复制代码发布无营养题解的行为，将被禁止相应权限！并扣除经验值! 申请恢复请联系管理员解除
本站题解请在题目内页-我要写题解发布，这样可以出现在题目题解列表页，还可以申请加优增加曝光哦！

李华

用户名：2645479600

访问量：4768

签　名：

qq:2645479600，欢迎共同探讨

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

　　自我简介：

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

TA的其他文章

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

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

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

你可能喜欢

简单的a+b （C语言代码）
浏览：408

【C语言训练】计算一个整数N的阶乘（C语言代码）
浏览：660

三进制小数（C语言代码）
浏览：784

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

C语言程序设计教程（第三版）课后习题11.12 （C语言代码）
浏览：600

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

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

原题链接：[蓝桥杯][基础练习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分

27 人评分

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

　　评论区

小白

厉害

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

斯宾塞

写的很详细 啊  谢谢大佬

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

正熠的伙伴

厉害

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 | |

精彩推荐

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）浏览：300

A+B for Input-Output Practice (IV) （C语言代码）浏览：371

求组合数（C语言代码）浏览：834

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）浏览：501

【矩阵】（C++代码）浏览：677

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）浏览：437

【C语言训练】亲密数（C语言代码）浏览：612

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

关于C语言变量位置的问题浏览：201

[蓝桥杯][历届试题]翻硬币（C++代码）浏览：772