102114: [AtCoder]ABC211 E - Red Polyomino
Description
Score : $500$ points
Problem Statement
You are given a grid with $N$ rows and $N$ columns, where the square at the $i$-th row from the top and $j$-th column from the left is painted black if $S_{i, j}$ is # and white if $S_{i, j}$ is ..
You will choose $K$ of the white squares and paint them red. How many such ways to paint the grid satisfy the following condition?
- The squares painted red will be connected. That is, you will be able to get from any red square to any red square by repeatedly moving horizontally or vertically while only visiting red squares.
Constraints
- $1 \leq N \leq 8$
- $1 \leq K \leq 8$
- Each $S_{i, j}$ is
#or.. - $N$ and $K$ are integers.
Input
Input is given from Standard Input in the following format:
$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}$
Output
Print the answer.
Sample Input 1
3 5 #.# ... ..#
Sample Output 1
5
We have five ways to satisfy the condition as shown below, where @ stands for a red square.
#.# #@# #@# #@# #@# @@@ .@@ @@. @@@ @@@ @@# @@# @@# .@# @.#
Note that the way shown below does not satisfy the connectivity requirement since we do not consider diagonal adjacency.
#@# @.@ @@#
Sample Input 2
2 2 #. .#
Sample Output 2
0
There is no way to satisfy the condition.
Sample Input 3
8 8 ........ ........ ........ ........ ........ ........ ........ ........
Sample Output 3
64678
Input
题意翻译
## 题目翻译  给你边长为 $ N $ 的且仅由字符 `#` 和 `.` 组成的正方形阵列，其中 `#` 表示黑色格子， `.` 表示白色格子。  你需要在白色格子中选择 $ K $ 个涂成红色，且使红色格子互相连接（仅包括上下左右相邻），求有多少种可能的方案。 ## 输入格式 第一行一个整数 $ N $ 第二行一个整数 $ K $ 以下 $ N $ 行每行 $ N $ 个字符表示给出的阵列 ## 输出格式 可能的答案Output
分数：500分
问题描述
给你一个有N行N列的网格，其中从上数第i行，从左数第j列的方块，如果Si, j是#，则涂成黑色，如果Si, j是.，则涂成白色。
- 你将选择K个白色方块并将它们涂成红色。有多少种这样的涂色方法满足以下条件？
约束条件
- 1 ≤ N ≤ 8
- 1 ≤ K ≤ 8
- 每个Si, j是
#或.。 - 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