E - 红色多米诺骨牌

得分：500分

问题描述

给定一个$N$行$N$列的网格，其中第$i$行（从上往下）第$j$列（从左往右）的方格如果$S_{i, j}$是#则涂黑，如果$S_{i, j}$是.则涂白。
您需要选择$K$个白色方块，并将其涂成红色。有多少种涂色方式满足以下条件？

• 涂成红色的方块连通。也就是说，您可以通过水平或垂直移动而只访问红色方块，从一个红色方块到达任何另一个红色方块。

约束

• $1 \leq N \leq 8$
• $1 \leq K \leq 8$
• 每个$S_{i, j}$要么是#要么是.
• $N$和$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

我们有五种满足条件的涂色方式，如下所示，其中@表示红色方块。

``` #.# #@# #@# #@# #@# @@@ .@@ @@. @@@ @@@ @@# @@# @@# .@# @.# ```

请注意，下图所示的涂色方式不满足连通性要求，因为我们不考虑对角线相邻。

``` #@# @.@ @@# ```

---

2
2
#.
.#

0

没有满足条件的涂色方式。

---

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

64678