Red Polyomino

题目描述

给你一个有 $N$ 行 $N$ 列的网格，第 $i$ 行第 $j$ 列的方格如果 $S_{i, j}$ 为 # 则被涂成黑色，如果 $S_{i, j}$ 为 $.$ 则为白色。
你将选择 $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
#.
.#

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

$1 \leq N \leq 8$ $1 \leq K \leq 8$ 每个 $S_{i, j}$ 为 # 或 $.$ 。 $N$ 和 $K$ 为整数。下面展示的有五种满足条件的方式，其中 $@$ 代表一个红色方格。

注意下面展示的方式不满足连通性的要求，因为我们不考虑对角线相邻。
不存在满足条件的方式。

标签: AtCoder|abc211E

AtCoder|abc211E