1868: 连接草坪(II)

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:132 通过:38

题目描述

在N×M的地图上,X表示草,.表示土地。
一个X与上下左右的X相连形成一片草坪。
现在已知地图上有三片草坪,最少需要将多少个单位上的土地变成草,才能把两块草坪连接成一块草坪。

输入格式

输入第一行为正整数N和M,不超过50。
接下来N行,每行M个字符。

输出格式

输出一个数字表示答案。

输入样例 复制

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

输出样例 复制

4

数据范围与提示

来源:USACO 2011.11
样例解释:
................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
...*....XXXXX...
..XXX....XXX....