Score : $500$ points

问题陈述

你得到一个 $N$ 行和 $N$ 列的网格，其中从上到下第 $i$ 行、从左到右第 $j$ 列的方格，如果 $S_{i, j}$ 为 #，则涂成黑色；如果 $S_{i, j}$ 为.，则涂成白色。

你需要从白色方格中选出 $K$ 个，并将它们涂成红色。有多少种涂色方式满足以下条件？

• 涂成红色的方格彼此相连。也就是说，你可以通过仅访问红色方格并不断水平或垂直移动，从任意一个红色方格到达其他任意一个红色方格。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 09:26:09