搜索 >>P1219 [USACO1.5] 八皇后 Checker Challenge

P1219 [USACO1.5] 八皇后 Checker Challenge 链接此处

一句话题意

在\(n*n\)的网格中,保证每行每列和每条斜线上只有一个皇后,统计方案数并输出字典序前三个方案

关键

没有给定具体n值,不能用for循环,如果一个个地去考虑有没有皇后,那就用DFS
但是DFS进去以后,方案已经固定,要让方案吃后悔药,就要用到回溯,以及回溯标记

// int heng[N],shu[N],ltor[N],rtol[N];
//  每行的坐标; 列,   左斜线  右斜线 是否有人
void dfs(int x)
{
	if(x==n+1)//当枚举皇后数量超标了的时候:递归出口
	{
		print();//打印字典序前三排列,DFS枚举出来的结果一定按字典序
		return;
	}
	for(int y=1;y<=n;y++)//对于每一行,我们枚举皇后的y值
		if(shu[y]==0 and ltor[x-y+n]==0 and rtol[x+y-1]==0)//当没有其他皇后干扰
//						对应左斜线号        右斜线号
		{
			heng[x]=y;//标记皇后位置,便于输出
			shu[y]=1,ltor[x-y+n]=1,rtol[x+y-1]=1;//标记这些列和斜线都有人了
			dfs(x+1);//递归考虑下一个皇后
			heng[x]=0;//回溯!
			shu[y]=0,ltor[x-y+n]=0,rtol[x+y-1]=0;//抹除这个皇后的所有影响,才能列举下一个位置
		}
}

知识网络

加强版:
搜索=>回溯=>统计方案问题