AT_abc211_e [ABC211E] Red Polyomino

题目描述

题目翻译

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

输入格式

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

输出格式

可能的答案

输入输出样例 #1

输入 #1

3
5
#.#
...
..#

输出 #1

5

输入输出样例 #2

输入 #2

2
2
#.
.#

输出 #2

0

输入输出样例 #3

输入 #3

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

输出 #3

64678