Type: Default 500ms 256MiB

土木学长

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

平头哥觉得打ACM太难了,于是跑去工地打灰去了。

经过几年工地生涯,平头哥现在接到一个造桥工程。

题目描述

我们需要在两地造一座大桥,促进两地交流。

现给你一个n x m的字符矩阵表示地图

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

其中X表示陆地, .....表示海水。

如果这两个 X 在垂直或者在水平方向上相邻(那么对角相邻不算),则定义它们属于同一个陆地,上图表示两块陆地。

平头哥为了赚钱,想让桥的长度尽量短。则上面样例平头哥只需在三个区域造桥梁即可,(桥梁用*表示)

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

请你帮平头哥求出桥的最小长度(平头哥发家致富就靠你了

输入格式

第一行两个整数,n和m。

接下来n行表示地图

数据范围1<=n,m<=501 <= n,m <= 50

输出格式

桥梁的最短长度

输入样例

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

输出样例

3

时间限制500 ms

2024周赛第一场

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
6
Start at
2024-11-30 14:00
End at
2024-11-30 17:00
Duration
3 hour(s)
Host
Partic.
24