给定一个n*m钻石矿区，你需要挖一些地道将所有的钻石挖出来：
一条地道是一条从边境出发的折线，途中覆盖的钻石都算采到，两条折线不能相交，但可以相邻，求最小的地道总长度
| 题目名称 | 2094. [UVA 10605]钻石矿道 |
|---|---|
| 输入输出 | uva10605.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 3000 ms (3 s) |
| 内存限制 | 162 MiB |
| 测试数据 | 10 |
| 题目来源 |
 mikumikumi
于2016-02-29加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：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楼
| ||||
【题目描述】
【输入格式】
多组数据，第一行为一个T(T<=10)，之后有T组数据。
每组数据第一行为两个整数n，m（3<=n,m<=11).
之后的n行，每行有m个字符,"."代表石头，"*"代表钻石，"#"代表矿区的边界。
【输出格式】
对于每组数据，输出最小的地道总长度。
【样例输入】
3 11 11 ########### ##.######## #....###### #.*....#### #..*.....## ##....*...# ###....**.# ###.......# ###..*...## ####...#### ########### 3 11 ########### #..*..*...# ########### 11 11 ########### ##.######## #....###### #.*....#### #..*.....## ##....*...# ###....**.# ###....*..# ###..*...## ####...#### ###########
【样例输出】
11 2 13
【提示】
对于第一组数据
我们可以这样挖地道