题目描述

$N$ 行 $N$ 列のマス目が与えられ、上から $i$ 番目、左から $j$ 番目のマスは、$S_{i,\ j}$ が # なら黒く塗られており、. なら白く塗られています。
あなたは白く塗られたマスのうち、ちょうど $K$ 個のマスを選んで赤く塗ります。以下の条件が満たされる塗り方は何通りありますか？

• 赤く塗られたマス(以下赤マスと呼ぶ)は連結である。すなわち、どの赤マスからどの赤マスへも赤マスのみを上下左右に辿って到達できる。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $S_{1,\ 1}S_{1,\ 2}\ \dots\ S_{1,\ N}$ $S_{2,\ 1}S_{2,\ 2}\ \dots\ S_{2,\ N}$ $\vdots$ $S_{N,\ 1}S_{N,\ 2}\ \dots\ S_{N,\ N}$

输出格式

答えを出力せよ。

题目大意

题目翻译

 给你边长为 $N$ 的且仅由字符 # 和 . 组成的正方形阵列，其中 # 表示黑色格子， . 表示白色格子。
 你需要在白色格子中选择 $K$ 个涂成红色，且使红色格子互相连接（仅包括上下左右相邻），求有多少种可能的方案。

输入格式

第一行一个整数 $N$
第二行一个整数 $K$ 以下 $N$ 行每行 $N$ 个字符表示给出的阵列

输出格式

可能的答案

3
5
#.#
...
..#

5

2
2
#.
.#

0

8
8
........
........
........
........
........
........
........
........

64678

提示

制約

• $1\ \leq\ N\ \leq\ 8$
• $1\ \leq\ K\ \leq\ 8$
• $S_{i,\ j}$ は # または .
• $N$ , $K$ は整数である

Sample Explanation 1

#.# #@# #@# #@# #@# @@@ .@@ @@. @@@ @@@ @@# @@# @@# .@# @.# 上のように条件を満たす塗り方が $5$ 通りあります。 赤マスを @ で表しました。 #@# @.@ @@# 上の塗り方は連結でないので条件を満たしません。 斜めのマス同士は連結していないことに注意してください。

Sample Explanation 2

条件を満たす塗り方はありません。