题目名称	2094. [UVA 10605]钻石矿道
输入输出	`uva10605.in/out`
难度等级	★★☆
时间限制	3000 ms (3 s)
内存限制	162 MiB
测试数据	10
题目来源	mikumikumi 于2016-02-29加入
开放分组	全部用户
提交状态
分类标签	状态压缩搜索法 K短路
	分享题解

通过：7，提交：18，通过率：38.89%
Shirry	100	0.010 s	0.37 MiB	C++
栋霸霸	100	0.087 s	0.40 MiB	C++
lyqlyqcogs	100	0.093 s	0.40 MiB	C++
MLE	100	0.100 s	0.40 MiB	C++
mikumikumi	100	0.102 s	0.42 MiB	C++
Andres_Lionel	100	0.235 s	15.79 MiB	C++
Andres_Lionel	100	0.246 s	15.79 MiB	C++
Andres_Lionel	90	0.330 s	13.88 MiB	C++
Andres_Lionel	40	0.784 s	15.79 MiB	C++
栋霸霸	0	0.000 s	0.29 MiB	C++

关于钻石矿道的近10条评论(全部评论)
为什么一个不低于O(2^钻矿个数)的算法也能过啊喂……数据的节操呢…… cstdio 2017-01-31 18:19 2楼
0.0还以为是双倍经验。。。然而。。。这道题并没有数据。。。还是老老实实去bzoj1001交吧，或者cogs 752 Skyo 2016-01-12 15:40 1楼

2094. [UVA 10605]钻石矿道

★★☆ 输入文件：uva10605.in 输出文件：uva10605.out 简单对比
时间限制：3 s 内存限制：162 MiB

【题目描述】

给定一个n*m钻石矿区，你需要挖一些地道将所有的钻石挖出来：

一条地道是一条从边境出发的折线，途中覆盖的钻石都算采到，两条折线不能相交，但可以相邻，求最小的地道总长度

【输入格式】

多组数据，第一行为一个T(T<=10)，之后有T组数据。

每组数据第一行为两个整数n，m（3<=n,m<=11).

之后的n行，每行有m个字符,"."代表石头，"*"代表钻石，"#"代表矿区的边界。

【输出格式】

对于每组数据，输出最小的地道总长度。

【样例输入】

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

【样例输出】

11
2
13

2094. [UVA 10605]钻石矿道

【题目描述】

【输入格式】

【输出格式】

【样例输入】

【样例输出】

【提示】

【来源】

【题目来源】