1. 首页
  2. 题解列表
  3. 1460题题解

蓝桥杯基础练习VIP-2n皇后问题 （C++代码）

2000 阅读 6 评论
原题链接：蓝桥杯基础练习VIP-2n皇后问题


解题思路:

    2018/3/29 16：8
    首先理解八皇后，然后就是一个使用两个八皇后叠加的问题，通过多设置几个数组就可以实现2*n皇后的问题，注意定义数组记录是否访问这一行或者这一列的时候，数组的值要大一些，防止数组越界。

    然后就是一个最基本的DFS就可以了。

#include<cstdio>
#include<cstring>
int a[9][9],vis1[9],vis2[9],cnt,n;
int x1[19],x2[19],y1[19],y2[19];
void DFS(int dep)
{
	if(dep==n+1) { cnt++; return ;}
	for(int i=1;i<=n;i++)
	{
		if(!vis1[i] && a[dep][i] && !x1[dep+i] && !y1[dep-i+n])
		{
			vis1[i]=1; a[dep][i]=0; x1[dep+i]=1; y1[dep-i+n]=1;
			for(int j=1;j<=n;j++)
			{
				if(!vis2[j] && a[dep][j] && !x2[dep+j] && !y2[dep-j+n])
				{
					vis2[j]=1;a[dep][j]=0; x2[dep+j]=1; y2[dep-j+n]=1;
					DFS(dep+1);
					vis2[j]=0;a[dep][j]=1; x2[dep+j]=0; y2[dep-j+n]=0;
				}
			}
			vis1[i]=0; a[dep][i]=1; x1[dep+i]=0; y1[dep-i+n]=0;
		}
	}
}
int main(void)
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	DFS(1);
	printf("%d",cnt);
	return 0;
}


点赞(6)
　

0.0分

11 人评分

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

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

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

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

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

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

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

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

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)
数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)
点进来你会后悔的
点进来你会后悔的
简简单单的循环
简简单单的循环
简单的回文数
简单的回文数

评论列表 共有 6 条评论

冲进前五百冲鸭 4年前 回复TA 
@冲进前五百冲鸭 我这算什么厉害,大神才是真的厉害,我还要学很多呢,这个算法我自己都没做出来(狗头)
海洋之心 4年前 回复TA 
@冲进前五百冲鸭 能看懂别人写的算法的代码，说明你很厉害。
冲进前五百冲鸭 4年前 回复TA 
vis1 和 vis2    是检查黑白皇后是否存在同一列上
x1   和 x2       是检查黑白皇后是否在由左至右的对角线上
y1   和 y2       是检查黑白皇后是否在由右至左的对角线上
数组a是棋盘上是否能够继续摆放棋子的判断条件
冲进前五百冲鸭 4年前 回复TA 
如果大佬能给个注释就完美了
zzxkj 5年前 回复TA 
@霍青桐 不愧是大佬，n*n所以只判断限制条件多的就行了
霍青桐 5年前 回复TA 
求指教大神的约束条件。。。。