UVA10605 Mines For Diamonds

题目描述

PDF

在一座山中，有一个位于同一地质层的钻石矿床需要被开采。针对这个地质层，存在一个网格化的地震调查图。所有可能含有钻石矿床的网格方块都在此计划中标记出来。

为了开采钻石材料，矿井必须沿着地质层从外部挖掘。使用现有的机械设备，任何矿井只能从一个网格方块延伸到相邻的方块，方向可以是北、东、南或西。

出于安全原因，矿井不允许分支；因此，在一个矿井内，任何网格方块最多只能直接连接两个其他网格方块。请注意，仍然允许有两个矿井并行运行。钻探需要经济高效。解决方案应允许访问所有钻石矿床，同时涉及尽可能少的网格方块——包括矿床的位置。

输入格式

第一行给出 $N$，$M$ 表示矿区大小。下面 $N$ 行 $M$ 列，表示矿区，其中"*"表示为矿，"#"表示矿区的外边界，"."表示为空白点。矿区一定被"#"完全包围，且矿区内部一定没有"#"。

输出格式

输出仅有一行，为所有地道长度总和的最小值。

输入输出样例 #1

输入 #1

3
11 11
###########
##.########
#....######
#.*....####
#..*.....##
##....*...#
###....**.#
###.......#
###..*...##
####...####
###########
3 11
###########
#..*..*...#
###########
11 11
###########
##.########
#....######
#.*....####
#..*.....##
##....*...#
###....**.#
###....*..#
###..*...##
####...####
###########

输出 #1

11
2
13