Cutting Figure

题意翻译

### 题目背景 你有一块n×m的方格纸。其中有一些方格已被涂上颜色。 我们把已被涂上颜色的方格全部放入一个集合A内，A中所有的方格都是相互联通的（联通即任意两个方格之间都存在一条路径 路径上的每一个方格都是已涂上颜色的，并且每一个方格都与前一个方格有一条公共边）。 我们想知道 最少删除多少个方格 才能使这张方格纸上有颜色的方格不再联通。 根据定义，只有一个方格的集合或者不包含任何方格的集合也是联通的。 ### 输入 输入第一行包含两个数 n和m 分别代表方格纸的高和宽 接下来的n行 每行有m个字符： “#”表示已被涂色的方格； “.”表示未被涂色的方格。 输入的方格纸保证所有有颜色的方格都是相互连通的。 ### 输出 输出最少需要删除几个方格才能使图变得不联通， 假如无法做到 输出-1。

题目描述

You've gotten an $ n×m $ sheet of squared paper. Some of its squares are painted. Let's mark the set of all painted squares as $ A $ . Set $ A $ is connected. Your task is to find the minimum number of squares that we can delete from set $ A $ to make it not connected. A set of painted squares is called connected, if for every two squares $ a $ and $ b $ from this set there is a sequence of squares from the set, beginning in $ a $ and ending in $ b $ , such that in this sequence any square, except for the last one, shares a common side with the square that follows next in the sequence. An empty set and a set consisting of exactly one square are connected by definition.

输入输出格式

输入格式

The first input line contains two space-separated integers $ n $ and $ m $ ( $ 1<=n,m<=50 $ ) — the sizes of the sheet of paper. Each of the next $ n $ lines contains $ m $ characters — the description of the sheet of paper: the $ j $ -th character of the $ i $ -th line equals either "#", if the corresponding square is painted (belongs to set $ A $ ), or equals "." if the corresponding square is not painted (does not belong to set $ A $ ). It is guaranteed that the set of all painted squares $ A $ is connected and isn't empty.

输出格式

On the first line print the minimum number of squares that need to be deleted to make set $ A $ not connected. If it is impossible, print -1.

输入输出样例

输入样例 #1

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

输出样例 #1

2

输入样例 #2

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

输出样例 #2

2

说明

In the first sample you can delete any two squares that do not share a side. After that the set of painted squares is not connected anymore. The note to the second sample is shown on the figure below. To the left there is a picture of the initial set of squares. To the right there is a set with deleted squares. The deleted squares are marked with crosses.