P12260 [蓝桥杯 2024 国 Java B] 房屋建造
题目描述
有一个由 $N$ 行 $N$ 列方格组成的建筑用地，每个方格，我们用 `#` 表示这是一堵墙，`.` 表示是一片空地，其中只有在空地上才可以进行房屋建造。小蓝想要在这片区域上建造两个房屋：通过水平/垂直方向可以连通在一起的区域属于同一个房屋。由于建筑物料有限，小蓝最多只能在 $K$ 个空地上进行房屋建造，同时他希望自己的房屋面积尽可能的大，所以他必须用光所有的 $K$ 块空地来建造房屋。
请问一共有多少种不同的建造方案。
输入格式
第一行输入三个整数 $N$、$K$。
接下来输入 $N$ 行，每行输入一个长度为 $N$ 的字符串，表示方格布局。
输出格式
输出一个整数表示答案。
说明/提示
### 样例说明
- 对于样例 $1$：$K = 3$，但只有两个空地，所以没有符合题意的解，答案为 $0$。
- 对于样例 $2$，答案如下所示，我们用 `@` 表示建筑物：
```
@#. @#@ @#. .#@ .#@
.## @## @## @## .##
@@# ..# .@# @.# @@#
```
### 评测用例规模与约定
- 对于 $50\%$ 的评测用例：$1 \leq N \leq 5$，$1 \leq K \leq 5$。
- 对于 $100\%$ 的评测用例：$1 \leq N \leq 8$，$1 \leq K \leq 8$。