HDU 2553 状态压缩

N皇后问题

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 23888    Accepted Submission(s): 10639

Problem Description
在N*N的方格棋盘放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在与棋盘边框成45角的斜线上。
你的任务是,对于给定的N,求出有多少种合法的放置方法。
 
Input
共有若干行,每行一个正整数N≤10,表示棋盘和皇后的数量;如果N=0,表示结束。
 
Output
共有若干行,每行一个正整数,表示对应输入行的皇后的不同放置数量。
 
Sample Input
1
8
5
0
 
Sample Output
1
92
10
 
Author
cgf
 
Source
 
入门级搜索N皇后,不打表TLE无疑,最近学了状态压缩模仿着写了下,太神奇了这种操作!
唯一的缺点恐怕就是可读性太差= =但是位运算真的很快,强!
#include<bits/stdc++.h>
using namespace std;
int high,ans;
void dfs(int col,int z1,int z2)  //列  主对角线   副对角线
{
  if(col==high) {ans++;return;}   //列满了说明放满了,方案加一
  int can=(high&~(col|z1|z2));   //得到的数二进制中为1得位表示当前可放置(与high是为了防止越界,int只有32位爆了就不好玩了= =,超出棋盘的位置不必考虑)
  while(can){                          //只要还有可能的位置能放就继续
    int cur=(can)&((~can)+1);    //得到可放置的位置中最低的一位
    can=(can&(~cur));             //将这一位从所有的可能中去除
    dfs(col|cur,(z1|cur)>>1,(z2|cur)<<1);  //递归,算上这一位后的各个放置情况
  }
}
int main()
{
    int N,M,i,j,k;
    while(scanf("%d",&N)!=EOF&&N){
        ans=0;
        high=((1<<N)-1);
        dfs(0,0,0);
        printf("%d\n",ans);
    }
    return 0;
}
上一篇:《DSP using MATLAB》Problem 6.10


下一篇:【Lintcode】076.Longest Increasing Subsequence