102967: [Atcoder]ABC296 Ex - Unite

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

问题描述

我们有一个$N$行$M$列的网格，每个方格都被涂成黑色或白色。其中，至少有一个方格被涂成黑色。
网格的初始状态由长度为$M$的$N$个字符串$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}$共享一个边。
可以证明，在题目给出的约束下，高桥总是有一种方法可以实现他的目标。

约束条件

• $1 \leq N \leq 100$
• $1\leq M \leq 7$
• $N$和$M$都是整数。
• $S_i$是由#和.组成的长度为$M$的字符串。
• 给定的网格至少有一个方格被涂成黑色。

输入

输入将从标准输入以以下格式给出：

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$

输出

输出高桥需要涂多少个方格，使得涂成黑色的方格是连通的。

样例输入 1

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

样例输出 1

3

初始网格如下所示，其中$(i,j)$表示从上数第$i$行，从左数第$j$列的方格。

假设高桥将三个方格$(2,3),(2,4),(3,4)$（如下图中红色所示）涂成黑色。

然后，我们有以下涂成黑色的方格，包括一开始就涂成黑色的方格。这些方格是连通的。

无法通过将两个或更少的方格涂成黑色，使得涂成黑色的方格是连通的，因此答案为$3$。
注意，涂成白色的方格不必是连通的。

样例输入 2

3 3
###