/**
* @author wowpH
* @date 2019-9-14 19:54:16
*/
#include<stdio.h>
#include<string.h>
#define TRUE 1
#define FALSE 0
#define MAX_N 8
#define BOARD TRUE
#define BLANK FALSE
int board[MAX_N][MAX_N];// 棋盘,BOARD表示棋盘,BLANK表示空白
int n, k, solution;
int row[MAX_N];// 每行是否有棋子,TRUE表示有棋子,FALSE表示无棋子
int column[MAX_N];// 每列...同上
void backTrack(int left, int x) {// 回溯,left表示剩余棋子,x表示当前行
if (left == 0) {// 无多余棋子
++solution;// 方案数加1
return;
}
// 遍历x行及下方的棋盘
for (int i = x; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == BLANK) {// 空白
continue;// 不能放旗子
}
if (row[i] == TRUE || column[j] == TRUE) {// 行或列有棋子
continue;// 不能放旗子
}
// 当前位置可以放子,设为TRUE
row[i] = TRUE;
column[j] = TRUE;
// 棋子数减1,行数加1
backTrack(left - 1, i + 1);
// 复盘,设为无子
row[i] = FALSE;
column[j] = FALSE;
}
}
}
int main() {
while (scanf("%d %d", &n, &k) && n != -1 && k != -1) {
getchar();// '\n'
// 输入棋盘
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
char ch = getchar();
if (ch == '.') {
board[i][j] = BLANK;
} else if (ch == '#') {
board[i][j] = BOARD;
}
}
getchar();// '\n'
}
// 初始化
memset(row, FALSE, sizeof(row));
memset(column, FALSE, sizeof(column));
solution = 0;
backTrack(k, 0);// 回溯
printf("%d\n", solution);
}
return 0;
}