洛谷 P1219 题解

此题使DFS较为简单明了。注意：必须使用多个一维数组来存储斜边。

AC代码

#include <iostream>
#include <cstring>
#include <cmath>
#define MAX 100
using namespace std;
int vis[MAX],n,num=1,ans=0;
bool l1[MAX],l2[MAX],l3[MAX];
//l1:当前列是否放置,l2:当前左上开始的对角线是否放置(\),l3:当前右上开始的对角线是否放置(/)
int pri()//打印当前方案
{
	if(num>3)return 0;//保证只打印前三个
	for(int i=1;i<=n;++i)//循环vis数组
	{
		printf("%d ",vis[i]);
	}
	puts("");
	num++;
	return 0;
}
int mark(int x, int y,bool a)//如果a为1就给(x,y)打标记,如果a为0就给(x,y)取消标记
{
	vis[x]=y;
	l1[y]=a;
	l2[x-y+n]=a;
	l3[x+y]=a;
	return 0;
}
bool check(int x,int y)//检测(x,y)是否可以放置，可以返回1，不可以返回0
{
	if(l1[y]==1||l2[x-y+n]==1||l3[x+y]==1) return 0;
	return 1;
}
int sar(int deep)//dfs,deep既作为棋子数量，也作为当前行
{
	if(deep>n)//终止条件
	{
		ans++;
		pri();
		return 0;
	}
	for(int i=1;i<=n;++i)//遍历列
	{
		if(check(deep,i)==1)//检测是否符合条件
		{
			mark(deep,i,1);
			sar(deep+1);
			mark(deep,i,0);
		}
	}
	return 0;
}
int main()
{
	memset(vis,0,sizeof(vis));
	memset(l1,0,sizeof(l1));
	memset(l2,0,sizeof(l2));
	memset(l3,0,sizeof(l3));
	scanf("%d",&n);
	sar(1);
	printf("%d",ans);
	return 0;
}