#1004. 「USACO 2011.11 Silver」Cow Beauty Pageant

内存限制
512 MiB
时间限制
2000 ms
文件输入输出
pageant.in ≫ pageant.out
题目类型
传统
评测方式
文本比较
上传者 admin
题目来源 usaco

显示标签

题目描述

给定一个 的网格图,其中 X 可以组成个四连通块,. 是可以加上 X 的空格。

问图中至少加入多少个 X 才能使图中只包含一个 X 四连通块。

输入格式 pageant.in

第一行包含两个整数,

接下来 行,每行包含一个由 X. 组成的长度为 字符串,表示网格图。

输出格式 pageant.out

第一行包含一个整数,表示至少加入多少个 X 才能使图中只包含一个四连通块。

样例

输入

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

输出

4

解释

原来的连通块划分:

................
..1111....222...
...1111....22...
.1111......222..
........22222...
..333....222....

加入 4 个 X 后:

................
..1111....222...
...1111X...22...
.1111..XX..222..
...X....22222...
..333....222....

数据范围与提示