分数: 500 点
问题陈述
给你一个网格 N 行和 N 列,其中正方形位于 i从顶部开始的第行和 j如果满足以下条件,则从左数第 - 列被漆成黑色: S_{i, j} is # 和白色如果 S_{i, j} is ..
您将选择 K 白色方块并将其涂成红色。有多少种绘制网格的方法满足以下条件?
- 涂成红色的方块将被连接起来。也就是说,您将能够通过重复水平或垂直移动而仅访问红色方块,从任何红色方块到达任何红色方块。
约束
- 1 \leq N \leq 8
- 1 \leq K \leq 8
- 每个 S_{i, j} is
#or.. - 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}
输出
打印答案。
示例输入 1
3 5 #.# ... ..#
示例输出 1
5
我们有五种方法来满足条件,如下所示,其中 @ 代表红色方块。
#.# #@# #@# #@# #@# @@@ .@@ @@. @@@ @@@ @@# @@# @@# .@# @.#
请注意,下面所示的方式不满足连接性要求,因为我们不考虑对角邻接。
#@# @.@ @@#
示例输入 2
2 2 #. .#
示例输出 2
0
无法满足条件。
示例输入 3
8 8 ........ ........ ........ ........ ........ ........ ........ ........
示例输出 3
64678