← 返回题目列表

AtCoder · abc211_e

E. 红色多联骨牌

中文机器翻译题面 查看原题

分数: 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