Description

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

Input

输入含有多组测试数据。
每组数据的第一行是两个正整数，n,kn,k，用一个空格隔开，表示了将在一个n×nn×n 的矩阵内描述棋盘，以及摆放棋子的数目。 n<=8,k<=nn <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的 nn 行描述了棋盘的形状：每行有nn个字符，其中’#’ 表示棋盘区域，’ .’ 表示空白区域（数据保证不出现多余的空白行或者空白列）。

Output

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

Sample Input

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

Sample Output

2
1

Idea

典型的搜索算法，类似于八皇后问题，每次选择一行放棋子，对每一列作标记。摆放失败的条件是到最后一行放好了但是还没有把棋子放完，直接 returnreturn；成功的条件是有 kk 枚棋子已经放在了棋盘上，这时要更新可行的方案数。
模拟一下搜索的过程：
1.1 棋子第一行进行遍历，i=1i=1；标记第一行，当前摆放棋子数目cnt=1cnt=1，
1.2 棋子第二行进行遍历, i=2i=2；标记第二行，当前摆放棋子数目 cnt=2cnt=2；cnt=k，returncnt=k，return；清除第二行标记，摆放棋子数目cnt−−，cnt=1cnt--，cnt=1，
1.3 棋盘第三行开始遍历,i=3i=3；标记第三行，当前摆放棋子数目cnt=2cnt=2；cnt=k，returncnt=k，return；清除第三行标记，摆放棋子数目cnt−−，way=1cnt--，way=1
1.4 标记第四行，当前摆放棋子数目cnt=2cnt=2；cnt=k，returncnt=k，return；清除第四行标记，摆放棋子数目cnt−−，cnt=1cnt--，cnt=1；从第一行开始的系列完全遍历，第一行进行清除标记，cnt−−,cnt=0cnt--,cnt=0，
每次遍历完全后，最后一行的DFS来开启下一行的遍历

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<cstring>
using namespace std;
const int N=12;
int n,k;
char map[N][N];
bool vis[N];
int ans;
int cnt;
void init()
{
	memset(vis,0,sizeof(vis));
	ans=0;
	cnt=0;
}
void dfs(int raw)
{
	if(cnt==k)
	{
		ans++;
		return;
	}
	if(raw>n) return;
	int i;
	for(i=1;i<=n;i++)
	{
		if(vis[i]||map[raw][i]=='.') continue;
		else
		{
			cnt++;
			map[raw][i]='.';
			vis[i]=1;
			dfs(raw+1);
			//回溯到上一层
			cnt--;
			vis[i]=0;
			map[raw][i]='#';
		}
	}
	dfs(raw+1);//开启下一个系列
}
void solve()
{
	init();
	int i,j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			cin>>map[i][j];
		}
	}
	dfs(1);
	cout<<ans<<endl;
}
int main()
{
	while(cin>>n>>k)
	{
		if(n==-1&&k==-1) break;
		else solve();
	}
	return 0;
}