#9299. 「USACO11NOV」Cow Beauty Pageant B - 题目

时间限制：1000 ms 内存限制：256 MiB 输入文件：pageant.in 输出文件：pageant.out

题目类型：传统评测方式：文本比较

上传者： root

登录后提交提交记录统计讨论题解

本题采用文件输入输出。

输入文件为 pageant.in，输出文件为pageant.out。

听说最近两斑点的奶牛最受欢迎，约翰立即购进了一批两斑点牛。

不幸的是，时尚潮流往往变化很快，当前最受欢迎的牛变成了一斑点牛。

约翰希望通过给每头奶牛涂色，使得它们身上的两个斑点能够合为一个斑点，让它们能够更加时尚。

牛皮可用一个的字符矩阵来表示，如下所示：

................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....

其中，表示斑点部分。

如果两个在垂直或水平方向上相邻（对角相邻不算在内），则它们属于同一个斑点，由此看出上图中恰好有两个斑点。

约翰牛群里所有的牛都有两个斑点。

约翰希望通过使用油漆给奶牛尽可能少的区域内涂色，将两个斑点合为一个。

在上面的例子中，他只需要给三个区域内涂色即可（新涂色区域用表示）：

................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
........XXXXX...
.........XXX....

请帮助约翰确定，为了使两个斑点合为一个，他需要涂色区域的最少数量。

从文件 pageant.in 中读入数据。

第一行包含两个整数和。

接下来行，每行包含一个长度为的由和构成的字符串，用来表示描述牛皮图案的字符矩阵。

输出到文件 pageant.out 中。

输出需要涂色区域的最少数量。

样例输入

6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....

样例输出

#9299. 「USACO11NOV」Cow Beauty Pageant B 普及−