logo AlgoBeat OnlineJudge
登录 注册

#10119. 三个连通块

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: AlgoBeat 官方账号

题目描述

感谢 @tanghaocheng 提供了本题的数据!

给出一个 的图。整幅图由 X. 构成。其中 X 在图中构成三个四连通块。问将这三个 X 连通块连成一个,最少需要将多少个 . 改成 X

四连通块是指左右上下相连。

输入格式

第一行包括两个整数 ,分别表示图的行数、列数。

接下来的 行,每行包括一个长度为 的字符串。

输出格式

输出包含一个整数,表示最少需要将多少个 . 改成 X

样例

输入输出样例 #1

输入 #1

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

输出 #1

4

数据范围与提示

对于 的数据,保证 , 字符串均由 X. 构成。