#P1410. Uva10605 Mines For Diamonds

    ID: 422 传统题 1000ms 512MiB 尝试: 145 已通过: 24 难度: 9 上传者: 标签>CF2600省选/NOI-插头 DP插头连通性编码轮廓状态规范化子集 DP估价下界剪枝哈希表

Uva10605 Mines For Diamonds

题目描述

给出山体某一地层的网格勘测图。含钻石的山体格子用 * 表示,其他山体格子用 . 表示,山体外部及补齐行宽的位置用 # 表示。所有 # 都属于可从外部到达的区域。

为了到达全部钻石,需要开挖若干条矿道。本站恢复版将合法方案明确为:

  • 每条矿道是一条由山体格子组成的简单路径,相继格子必须上下左右相邻。同一矿道不能分叉、形成环或重复使用一个格子。
  • 每条矿道至少有一个端点与 # 上下左右相邻,表示从山体外进入;另一个端点可以留在山体内,也可以邻接外部。一个邻接 # 的山体格子可以单独构成矿道。
  • 不同矿道不能共用山体格子,因而不能相交或重合。不同矿道可以平行,也可以占用彼此相邻的格子;相邻并不表示自动开通连接,连接只由各条路径选取的相邻步决定。
  • 每个 * 必须属于一条矿道。代价为所有矿道实际占用的山体格子总数,* 和 . 均各计一个,# 不计。由于矿道不共格,不存在共用格子的重复计费或免费共享。

求合法方案的最小代价。若没有钻石,可以不开挖任何矿道,答案为 0。

输入格式

本题采用单组数据输入。

第一行两个整数 n,mn,m。接下来 nn 行,每行恰好 mm 个字符,表示矿区。

输出格式

一行一个整数,表示最少挖掘格子数。

数据范围

3≤n,m≤113\le n,m\le11;有 00 到 1010 个钻石格子。地图被 # 包围。保证存在可行方案,且最优方案使用的山体格子不超过 2020 个。

样例

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

来源与本站格式

题目背景、移动方向、平行矿道及原始范围来自 UVA 10605 官方题面。本站采用单组输入,并保留原测试中没有钻石的情况;矿道相交与计数按上面明确列出的本站恢复版规则执行。