← 返回题目列表

Codeforces · 193/A

A. 切割图

中文机器翻译题面 查看原题

你得到了一张 n × m 的方格纸。它的一些方块被涂漆了。让我们将所有绘制的正方形的集合标记为 A。集合 A 是连通的。你的任务是找到我们可以从集合 A 中删除以使其不连通的最小方块数。

一组绘制的方块被称为连通的,如果对于该组中的每两个方块 a 和 b,该组中存在一系列方块,从 a 开始,以 b 结束,这样在该序列中,除了最后一个方块之外的任何方块都与序列中下一个方块共享公共边。根据定义,空集和仅由一个正方形组成的集是相连的。

输入

第一个输入行包含两个空格分隔的整数 n 和 m (1 ≤ n, m ≤ 50) — 纸张的尺寸。

接下来的 n 行中的每一行都包含 m 个字符 — 纸张的描述:如果相应的方块被绘制(属于集合 A),则第 i 行的第 j 个字符等于“#”,或者等于“。”如果对应的方块没有被绘制(不属于集合A)。保证所有被绘制的方块A的集合是连通的并且不为空。

输出

在第一行打印需要删除以使 A 组不连通的最小方格数。如果不可能,则打印-1。

示例

输入 #1

5 4
####
#..#
#..#
#..#
####

输出 #1

2

输入 #2

5 5
#####
#...#
#####
#...#
#####

输出 #2

2

注意

在第一个示例中,您可以删除任意两个不共享边的正方形。之后,这组绘制的方块就不再连接了。

第二个示例的注释如下图所示。左边有一张初始正方形集的图片。右侧有一组已删除的方块。删除的方块标有十字。