学步园

//很经典的回溯题目，要好好学习递归的思想
#include<iostream>
using namespace std;
int mat[8][8];
int rr[8];
int cc[8];
char ch;
int n,k,res;
int time;

//t表示所在的行
void backtrace(int t){
	if(time==k){
		res++;
		return;
	}
	if(t>=n)
		return;
	for(int i=0;i<n;i++){
		if(mat[t][i]==1){
			if(!rr[t]&&!cc[i]){
				time++;
				rr[t]=cc[i]=1;
				backtrace(t+1);
				time--;
				rr[t]=cc[i]=0;
			}
		}
	}
	backtrace(t+1);//=======================很关键的作用
}

int main()
{
	while(scanf("%d%d",&n,&k)!=EOF){
		if(n==-1&&k==-1)
			break;
		getchar();
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				scanf("%c",&ch);
				if(ch=='#'){
					mat[i][j]=1;
				}
				if(ch=='.')
					mat[i][j]=0;
			}
			getchar();
		}
		res=time=0;
		memset(rr,0,sizeof(rr));
		memset(cc,0,sizeof(cc));
		backtrace(0);
		printf("%d\n",res);
	}
}