棋盘问题

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 66277		Accepted: 31639

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。

输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n

当为-1 -1时表示输入结束。

随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。

2 1

#.

.#

4 4

...#

..#.

.#..

#...

-1 -1

2

1

#include<cstdio>

#include<string>

#include<cstdlib>

#include<cmath>

#include<iostream>

#include<cstring>

#include<set>

#include<queue>

#include<algorithm>

#include<vector>

#include<map>

#include<cctype>

#include<stack>

#include<sstream>

#include<list>

#include<assert.h>

#include<bitset>

#include<numeric>

#define max_v 10

char G[max_v][max_v];

int M[max_v];

int c,n,k;

void init()

{

    c=;

    memset(M,,sizeof(M));

}

void dfs(int row,int num)

{

   if(num==k)

   {

       c++;

       return ;

   }

   for(int i=row+;i<=n;i++)

   {

       for(int j=;j<=n;j++)

       {

           if(G[i][j]=='#'&&M[j]==)

           {

               M[j]=;

               dfs(i,num+);

               M[j]=;

           }

       }

   }

}

int main()

{

    while(~scanf("%d %d",&n,&k))

    {

        if(n<&&k<)

            break;

        for(int i=;i<=n;i++)

            scanf("%s",G[i]+);

        init();

        dfs(,);

        printf("%d\n",c);

    }

    return ;

}