红色多联骨牌

题目描述

给定一个 $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}$

输出格式

输出答案。

样例

3
5
#.#
...
..#

5

满足条件的涂法有 5 种,如下图所示,其中 @ 表示红色格子：

#.# #@# #@# #@# #@#
@@@ .@@ @@. @@@ @@@
@@# @@# @@# .@# @.#

注意,由于不考虑斜向相邻,下图的涂法不满足连通性要求：

#@#
@.@
@@#

2
2
#.
.#

0

不存在满足条件的涂法。

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

64678

数据范围

• $1 \le N \le 8$
• $1 \le K \le 8$
• 每个 $S_{i, j}$ 都是 # 或 .
• $N$ 和 $K$ 均为整数