HDU2553N皇后问题（状态压缩）

这道题其实最简单的方法就是打表，直接DFS会超时，那就先运行一遍，找出1~10的值，打表即可，这里提供DFS和打表的数据

DFS：（白书上的）TLE

 1 #include <stdio.h>
 2 #include <string.h>
 3 int vis[3][25],ans,n;
 4 
 5 void dfs(int cur)
 6 {
 7     if(cur == n){ans++;return;}
 8     for(int i=0;i<n;i++)
 9     {
10         if(!vis[0][i] && !vis[1][i+cur] && !vis[2][cur-i+n])
11         {
12             vis[0][i] = vis[1][i+cur] = vis[2][cur-i+n] = 1;
13             dfs(cur+1);
14             vis[0][i] = vis[1][i+cur] = vis[2][cur-i+n] = 0;
15         }
16     }
17 }
18 
19 
20 int main()
21 {
22     while(~scanf("%d", &n) && n)
23     {
24         ans = 0;
25         memset(vis,0,sizeof(vis));
26         dfs(0);
27         printf("%d\n", ans);
28     }
29     return 0;
30 }

打表 ans[11] = {0,1,0,0,2,10,4,40,92,352,724};

 1 #include <stdio.h>
 2 #include <string.h>
 3 int ans[11] = {0,1,0,0,2,10,4,40,92,352,724};
 4 int main()
 5 {
 6     int n;
 7     while(~scanf("%d", &n) && n)
 8     {
 9         printf("%d\n",ans[n]);
10     }
11     return 0;
12 }

之后，听了章爷的想法后，发现状态压缩可以过

8821841

2013-08-03 21:56:38

Accepted

2553

703MS

228K

517 B

C++

塔罗

由于给的数据范围比较小（而且也只能这么小），所以我们可以用一个数来表示上面代码中的已标记的列，主对角线，和副对角线，如果不太熟悉位运算的，可以先看看位运算，感觉位运算都是自己感觉着写，那些常用的我也还是不记得==！。

我们用Col，First和Second分别表示标记了列，主对角线和副对角线的值，初始时全为0，这样的话(Col | First | Second)就表示到当前列时已经标记了的（不能放皇后的）点，那我们对其取反~操作，也就是CanPut = ~（Col| First | Second），那得到的数就表示可以放的位置，所有1所在的位置也就是可以放的位置，那我们每次取出最低位的1(x & (-x))（这个我之前也不知道，网上查到的），那这样的话就得出了当前所有可以放的位置（不用像上面一个一个判断）（如果可以的话，尽可能自己推出递推关系，这里并不难）。

这里要注意的一个问题就是取反（~）操作之后，由于它高于N的位置也被置为了1，也就是相当于放到了某一行的棋盘的外面去了，所以我设置了一个值High = (1<<N)-1，然后每次得到一个可以放的位置的值CanPut，就对其和High取与（&）运算，这样的话就可以去掉高位的1，得到的数都是High以内的。

然后就是要处理已经处理了此行如何进行递归倒下一行的问题，假设在本行取出了一个CanPut的最低位LowBit，那么到下一行时，下一行的Col就是Col | LowBit，当前行的First倒下一行时由于所有标记的点都往右移了一格，所以First>>1，再加上LowBit的右边一格也不能放，所以下一行主对角线已经标记了的就是（First>>1 | LowBit>>1），同理，副对角线标记了的就是（Second<<1 | LOwBit <<1）.

由上面的公式，下面的例子可以加深理解

 1 #include <stdio.h>
 2 int N,ans,High;
 3 void DFS(int Col,int Fir,int Sec)
 4 {
 5     if(Col == High){ans++;return;}//所有的列都已经被标记了，说明没咧都放了
 6     int CanPut = ((~(Col | Fir | Sec)) & High);
 7     while(CanPut)
 8     {
 9         int LowBit = CanPut & (-CanPut);//取出最低位
10         DFS((Col|LowBit), ((Fir|LowBit)>>1), (((Sec|LowBit) <<1) & High));
11         CanPut &= (~LowBit);//去掉最低位
12     }
13 }
14 
15 int main()
16 {
17     while(~scanf("%d", &N) && N)
18     {
19         High = (1<<N)-1;  ans = 0;
20         DFS(0,0,0);
21         printf("%d\n", ans);
22     }
23     return 0;
24 }

HDU2553N皇后问题（状态压缩）

推荐阅读