Score : $600$ points

问题描述

我们有一个包含 $N$ 行和 $M$ 列的网格，其中每个格子被涂成黑色或白色。这里至少有一个格子是黑色的。

网格的初始状态由 $N$ 个长度为 $M$ 的字符串 $S_1,S_2,\ldots,S_N$ 给出。如果第 $i$ 行（从上到下数）和第 $j$ 列（从左到右数）的格子对应字符 $S_i$ 的第 $j$ 个字符是 #，则该格子被涂成黑色；如果是.，则被涂成白色。

高桥想要重新涂色一些白色格子（可能为零个），使得所有涂黑的格子都是连通的。请找出他需要重新涂色的格子的最小数量以实现他的目标。

在这里，若每一对涂黑的格子 $(S,T)$ 存在一个正整数 $K$ 和一个包含 $K$ 个黑色格子的序列 $X=(x_1,x_2,\ldots,x_K)$，满足 $x_1=S$、$x_K=T$ 且对于所有 $1\leq i\leq K-1$，$x_i$ 和 $x_{i+1}$ 都有一条公共边，则称这些涂黑的格子是连通的。

可以证明，在本问题的约束条件下，高桥总有一种方法能够实现他的目标。

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

Problem Statement

We have a grid with $N$ rows and $M$ columns, where each square is painted black or white. Here, at least one square is painted black.
The initial state of the grid is given as $N$ strings $S_1,S_2,\ldots,S_N$ of length $M$.
The square at the $i$-th row from the top and $j$-th column from the left is painted black if the $j$-th character of $S_i$ is #, and white if it is ..

Takahashi wants to repaint some white squares (possibly zero) black so that the squares painted black are connected. Find the minimum number of squares he needs to repaint to achieve his objective.

Here, the squares painted black are said to be connected when, for every pair of squares $(S,T)$ painted black, there are a positive integer $K$ and a sequence of $K$ squares $X=(x_1,x_2,\ldots,x_K)$ painted black such that $x_1=S$, $x_K=T$, and $x_i$ and $x_{i+1}$ share a side for every $1\leq i\leq K-1$.
It can be proved that, under the constraints of the problem, there is always a way for Takahashi to achieve his objective.

Constraints

• $1 \leq N \leq 100$
• $1\leq M \leq 7$
• $N$ and $M$ are integers.
• $S_i$ is a string of length $M$ consisting of # and ..
• The given grid has at least one square painted black.

Input

The input is given from Standard Input in the following format:

$N$ $M$

$S_1$

$S_2$

$\vdots$

$S_N$

Output

Print the minimum number of squares that Takahashi needs to repaint for the squares painted black to be connected.

Sample Input 1

3 5
...#.
.#...
....#

Sample Output 1

3

The initial grid looks as follows, where $(i,j)$ denotes the square at the $i$-th row from the top and $j$-th column from the left.

Assume that Takahashi repaints three squares $(2,3),(2,4),(3,4)$ (shown red in the figure below) black.

Then, we have the following squares painted black, including the ones painted black from the beginning. These squares are connected.

It is impossible to repaint two or fewer squares black so that the squares painted black are connected, so the answer is $3$.
Note that the squares painted white do not have to be connected.

Sample Input 2

3 3
###
###
###

Sample Output 2

0

All squares might be painted black from the beginning.

Sample Input 3

10 1
.
#
.
.
.
.
.
.
#
.

Sample Output 3

6

update @ 2024/3/10 12:19:27