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

DFS：（白书上的）TLE

1 #include 
     
       2 #include 
      
        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
      
     

打表  ans[11] = {

0,1,0,0,2,10,4,40,92,352,724};

 

1 #include 
     
       2 #include 
      
        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

703MS

228K

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 
     
       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<