P1562 还是N皇后

你的名字 2021-03-28 13:50 441阅读 0赞

# 神奇的位运算啊。。。 #

这道题显然不能用普通的回溯法解决。我们可以使用位运算。

框架同样采用dfs，但是使用了4个东西作为参数（使用二进制）：

1.  `line`作为当前在哪个位置已经放置了皇后（1表示已经放置，0表示可以放置）
2.  `ll`作为**当前已放置的皇后的左上右下对角线对当前行的影响（1表示不能放置，0表示可以放置）**
3.  `rr`作为**当前已放置的皇后的右上左下对角线对当前行的影响（1表示不能放置，0表示可以放置）**
4.  `now`作为当前dfs到了第几行（不使用二进制）

![200707261.gif][]  
![200707262.gif][]

对于普通无限制的八皇后，直接把上面三个用二进制表示的进行或运算，然后在进行按位非（`~`）操作，得到的有1的就是可以放置的地方了。

这道题有限制，直接把题目给的限制一起或一下就行了。

然后运用`lowbit`函数可以把第一个1取出来，进行下一步的dfs。

代码：

#include<cstdio> 
	#include<vector> 
	const int maxn = 17; 
	#define lowbit(x) (x & -x) 
	int stdd[maxn]; int all, n; 
	int ans; 
	void dfs(int i, int line, int ll, int rr) { 
		if(i == n + 1) { 
			ans++; 
			return; 
		} 
		int may = ~(stdd[i] | line | ll | rr); 
		may = all & may;
		//去掉那个左移溢出的 
		while(may) { 
			int temp = lowbit(may); 
			may -= temp; 
			dfs(i + 1, line + temp, (ll + temp) >> 1, (rr + temp) << 1);//左上右下对角线的影响要右移，右上左下的反之 
		} 
	} 
	int main() { 
	scanf("%d", &n); 
	all = (1 << n) - 1; 
	char ch[maxn]; 
	for(int i = 1; i <= n; i++) { 
		scanf("%s", ch + 1); 
		for(int j = 1; j <= n; j++) { 
			if(ch[j] == '.') stdd[i] = stdd[i] | (1 << (j - 1));
			//我这里的stdd其实是与题面镜像的，但是不影响答案 
		} 
	} 
	dfs(1, 0, 0, 0); printf("%d\n", ans); return 0; 
	}

[200707261.gif]: /images/20210328/1616939425898.gif
[200707262.gif]: /images/20210328/1616939400717.gif