n 皇后

n 皇后

描述

n 皇后问题：一个 n×n 的棋盘，在棋盘上摆n 个皇后，满足任意两个皇后不能在同一行、同一列或同一斜线上的方案有多少种？

输入

第一行包含一个整数 n。

输

输出一个整数，表示方案数。

样例 1 输入

样例 1 输

样例 2

请查看下发文件内的 sample2_input.txt 和 sample2_output.txt。

限制

一共 10 个测试点， 第i 个测试点的 n=i+4。时间：2 sec

空间：512 MB

提示

python 同学注意，标程后两个测试点 10s 都过不去，故自行打表。

[考察剪枝水平，剪枝剪得好（二进制剪枝）的才能过第 10 个测试点。]

代码

#include <iostream>

#pragma warning(disable:4996) using namespace std;

// ================= 代码实现开始 =================

/* 请在这里定义你需要的全局变量 */

//ans:总答案

//allOne:用于二进制&的全1数int ans, allOne;

//搜索(用二进制来优化)

//pos:其二进制上的某个位置的1表示当前所在行的相应的位置(列)已经放了一个皇后

//left:其二进制上的某个位置的1表示当前所在行的相应的位置(是由于右对角线上已经有皇后)不 能放置皇后

//right:其二进制上的某个位置的1表示当前所在行的相应的位置(是由于左对角线上已经有皇后)不 能放置皇后

void dfs(int pos, int left, int right)

{

//if判定语句暂定，可能会有错误

if (pos== allOne)//当且仅当每一列都放了一个皇后那么整个棋盘已经放了n个合法皇后，故要终止

{

++ans;

return;

}

for (int t = allOne & (~(pos | left | right)); t;)//t表示可以放的集合对应的二进制数

{

int p = t & -t;//low bit:二进制最右边的1(负数为二进制原码取反加1，故通过此方法可以获得最低位的1)

dfs(pos | p, (left | p) << 1, (right | p) >> 1);

t ^= p;//消掉low bit

}

}

// 一个n×n的棋盘，在棋盘上摆n个皇后，求满足任意两个皇后不能在同一行、同一列或同一斜线上的方案数

// n：上述n

// 返回值：方案数

int getAnswer(int n) {

/* 请在这里设计你的算法 */

ans = 0;

allOne = (1 << n) - 1;

dfs(0, 0, 0);

return ans;

}

// ================= 代码实现结束 =================

int main() {

int n;

cin >> n;

cout << getAnswer(n) << endl;

return 0;

}