#P1410. Uva10605 Mines For Diamonds
Uva10605 Mines For Diamonds
题目描述
给出山体某一地层的网格勘测图。含钻石的山体格子用 * 表示,其他山体格子用 . 表示,山体外部及补齐行宽的位置用 # 表示。所有 # 都属于可从外部到达的区域。
为了到达全部钻石,需要开挖若干条矿道。本站恢复版将合法方案明确为:
- 每条矿道是一条由山体格子组成的简单路径,相继格子必须上下左右相邻。同一矿道不能分叉、形成环或重复使用一个格子。
- 每条矿道至少有一个端点与
#上下左右相邻,表示从山体外进入;另一个端点可以留在山体内,也可以邻接外部。一个邻接#的山体格子可以单独构成矿道。 - 不同矿道不能共用山体格子,因而不能相交或重合。不同矿道可以平行,也可以占用彼此相邻的格子;相邻并不表示自动开通连接,连接只由各条路径选取的相邻步决定。
- 每个
*必须属于一条矿道。代价为所有矿道实际占用的山体格子总数,*和.均各计一个,#不计。由于矿道不共格,不存在共用格子的重复计费或免费共享。
求合法方案的最小代价。若没有钻石,可以不开挖任何矿道,答案为 0。
输入格式
本题采用单组数据输入。
第一行两个整数 。接下来 行,每行恰好 个字符,表示矿区。
输出格式
一行一个整数,表示最少挖掘格子数。
数据范围
;有 到 个钻石格子。地图被 # 包围。保证存在可行方案,且最优方案使用的山体格子不超过 个。
样例
11 11
###########
##.########
#....######
#.*....####
#..*.....##
##....*...#
###....**.#
###.......#
###..*...##
####...####
###########
11
来源与本站格式
题目背景、移动方向、平行矿道及原始范围来自 UVA 10605 官方题面。本站采用单组输入,并保留原测试中没有钻石的情况;矿道相交与计数按上面明确列出的本站恢复版规则执行。