海洋之心


私信TA

用户名:wanggongsheng

访问量:122492

签 名:

等  级
排  名 17
经  验 20493
参赛次数 3
文章发表 163
年  龄 26
在职情况 学生
学  校
专  业 计算机技术

  自我简介:

读研ing,平时不登录dotcpp


解题思路:

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


 

0.0分

16 人评分

  评论区

vis1 和 vis2    是检查黑白皇后是否存在同一列上
x1   和 x2       是检查黑白皇后是否在由左至右的对角线上
y1   和 y2       是检查黑白皇后是否在由右至左的对角线上
数组a是棋盘上是否能够继续摆放棋子的判断条件
2020-02-29 08:59:41
如果大佬能给个注释就完美了
2020-02-29 08:35:19
求指教大神的约束条件。。。。
2019-01-23 09:42:22
  • «
  • 1
  • »