poj1321

Description

在一個給定形狀的棋盤（形狀可能是不規則的）上面擺放棋子，棋子沒有差別。要求擺放時任意的兩個棋子不能放在棋盤中的同一行或者同一列，請程式設計求解對于給定形狀和大小的棋盤，擺放k個棋子的所有可行的擺放方案C。

Input

輸入含有多組測試資料。

每組資料的第一行是兩個正整數，n k，用一個空格隔開，表示了将在一個n*n的矩陣内描述棋盤，以及擺放棋子的數目。 n <= 8 , k <= n

當為-1 -1時表示輸入結束。

随後的n行描述了棋盤的形狀：每行有n個字元，其中 # 表示棋盤區域， . 表示空白區域（資料保證不出現多餘的空白行或者空白列）。

Output

對于每一組資料，給出一行輸出，輸出擺放的方案數目C （資料保證C<2^31）。

Sample Input

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
      

Sample Output

2
1
----------------------------------------8皇後的變種-----------------------------------------------------------
我通過枚舉行，加上判斷是否能放在這一列。因為n<=8，是以可以采用一個int類型的變量利用位運算來存儲狀态。然後再遞歸實作。
2個簡單的剪枝：當已經擺放的棋子個數加上所剩的行數小于要求擺放的棋子個數時，剪枝；
當已經擺放的棋子個數加上所剩行中所有的棋子個數小于要求擺放的棋子個數時，剪枝；
通過預處理，計算出前i行的棋子總數(num[i]);

 
          
 
 #include<iostream>       
      
 using namespace std;       
      
 int n,m,sum,num[10];       
      
 char chess[10][10];       
      
 void init( )       
      
 {       
      
     int i,j;       
      
     memset(num,0,sizeof(num));       
      
     for ( i=0 ; i<n ; i++ )       
      
     {       
      
         scanf("%s",chess[i]);       
      
         for ( j=0 ; j<n ; j++ )       
      
             if ( chess[i][j]=='#' )       
      
                 num[i+1]++;       
      
         num[i+1]+=num[i];       
      
     }       
      
     sum=0;       
      
 }       
      
 void solve ( int line , int cnt , int mark )       
      
 {       
      
     int i;       
      
     if ( line==n )       
      
     {       
      
         if ( cnt==m )       
      
             sum++;       
      
         return ;       
      
     }       
      
     if ( cnt+num[n]-num[line]<m || n-line+1+cnt<m )       
      
         return ;       
      
     for ( i=0 ; i<n ; i++ )       
      
         if ( chess[line][i]=='#' && ((mark>>i)&1)==0 )       
      
             solve(line+1,cnt+1,mark|(1<<i));       
      
     solve(line+1,cnt,mark);       
      
 }       
      
 int main ( )       
      
 {       
      
     int i,j;       
      
     while( scanf("%d%d",&n,&m) && m!=-1 && n!=-1 )       
      
     {       
      
         init();       
      
         for ( i=0 ; i<n ; i++ )       
      
             for ( j=0 ; j<n ; j++ )       
      
                 if ( chess[i][j]=='#' )       
      
                     solve(i+1,1,1<<j);       
      
         printf("%d/n",sum);       
      
     }       
      
 }