Problem2611--Cow Beauty Pageant[USACO-2011-Nov-B]

2611: Cow Beauty Pageant[USACO-2011-Nov-B]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Status] [Submit] [Creator:]

Description

听说最近的流星趋势是奶牛的皮肤上有两个斑点,Farmer John买了一群两个斑点的奶牛。
但是,流行趋势变化很快,最近最流行的竟然是一个斑点的奶牛。
Farmer John想把牛身上的两个斑点画成一个斑点,从而使得他的那群牛变得更时尚。
牛的皮肤可以看做是N*M的字符网格(1≤N,M≤50):

每一个"X"代表一个斑点的一部分。
两个在垂直或者水平方向(对角线方向不算)相连的"X"属于同一个斑点,上述的图形中有两个斑点。
Farmer John的这群奶牛都有两个斑点,他想尽可能少的使用油漆来把两个斑点合并成一个斑点。
在上面的图形中,他可以只添加三个“X”就可以完成合并。
如下面的图形所示。为了更易说明,把增加的三个"X"用“*”来标记

请帮助Farmer John计算出把两个斑点合并成一个斑点,他需要增加的"X"的最小数量。

Input

输入的第一行,用空格隔开的两个整数N和M
接下来N行,每行M个字符,字符是"X"或者".",表示牛的皮肤的图形。

Output

输出一行,一个整数,表示把两个斑点合并成一个斑点,需要添加的“X”的最小数量

Sample Input Copy

<img src="http://cdl-asset.oss-cn-beijing.aliyuncs.com/online/ea6d3c1a221138065b48f4f7a91b662b.png" style="width: 122px;" class="fr-fic fr-dib fr-fil">

Sample Output Copy

3

HINT

样例说明:
输入样例中的图形,有两个斑点,我们分别用“1”和“2”来标记第一个斑点和第二个斑点

把两个斑点合并成1个斑点,需要添加3个“X”,如下所示

Source/Category