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