Description

国际象棋棋盘由黑白相间的格子组成，要把k个相同的棋子摆放在黑色区域内，摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列。

求对于给定的棋盘，摆放k个棋子的所有可行的摆放方案数。

Input Format

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

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

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

对于样例1:棋盘[0,0][1,1]两个位置都可以摆放棋子，要把1个棋子摆放在这两个位置，共2种方案。

对于样例2:棋盘[0,3][1,2][2,1][3,0]四个位置都可以摆放棋子，要把4个棋子摆放在这四个位置，共1种方案

Output Format

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

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

2
1​

Source

基础百练 搜索 dfs