N皇后问题2
提交数: 710, 通过率: 38.17%, 平均分: 64.73
题目描述:
现在要在N*N棋盘内放N个皇后,使任意两个皇后都不相吃。
皇后可以吃同一行,同一列,同一对角线的棋子。
输出所有的方案。
输入格式:
输入一个数N
输出格式:
输出所有的方案
样例输入:
4
样例输出:
2 4 1 3 3 1 4 2
提示:
4 <= N <= 13
qq1010903229 : 听说有些人在N皇后问题1中打表 0ms AC,于是我出了这道题。
算法提示:位运算优化
请完善程序:
#include <bits/stdc++.h>
using namespace std;
int n,a[50], all,ans;
void print() {
for(int i=1; i<=n; i++) {
int cnt = 0, c;
c = a[i]; //a[i]=8,那么cnt为4,即放在第4列上
while(c) { //算出2的几次方是a[i], 如a[i]=8,那么c为8,4,2,1,0,所以cnt的值为4
_______________
c = ( c >> 1 );
}
printf("%d ", cnt );
}
printf( "\n" );
return;
}
void dfs(int now,int r,int ld,int rd) { //列及两个方向的对角线
if( r == all ) { //每一列上全为1,也就是说没位置可放了,或写成 now>n
print( );
return;
}
int pos = all & _____________ ; //把当前第now行上不能放的列,排除掉
while( pos ) {
int p = pos & _____________; //把pos代表的可放列中都试放一遍,取最低位( 最右 )的1
pos ^= p; //把相应位(列)上的1置为0 或 pos -= p
______________; //a[i]记的是2的多少次的值,是2的(列号-1)次方的值
dfs(____________________); //对角线:/的对角线左移一列,\的对角线是右移一列
//每个放置的列p,对下行来说会影响到2*p 和 p/2的列
}
}
int main() {
cin >> n;
all = ( 1 << n ) - 1; // all为从第1列到第n列,全部为1
dfs( 1, 0, 0, 0 ); //第几行,后面是列及两个方向的对角线所覆盖的列号
return 0;
}
时间限制: 400ms空间限制: 16MB
来源: by qq1010903229