[UVA][搜索] 10605 - Mines For Diamonds
Within a mountain, a diamond deposit is to be recovered which is located in one and the same geological stratum. With regard to this stratum a gridded seismic survey exists. All the grid squares with supposed diamond deposits are marked in this plan.
Example:
In order to recover the diamond material, mines have to be dug along the stratum from the outside. Using the machinery available, any mine may only be continued from one grid square to the adjacent square in either a northward or eastward or southward or westward direction.
For safety reasons, mines are not permitted to branch out; so within a
mine there may not be any grid square with more than two directly
connected grid squares. Note that therefore it is still allowed to have
two mines running parallel.
Drilling is to proceed economically. A solution is called for that
allows
access to all diamond deposits while involving the lowest possible
number of
grid squares - including the places of deposits.
Here is a possible solution for the example:
Input
The first line of input contains a number T <=10 giving the number of cases to be dealt with. The following lines form the input for the T cases, each in the format described below.
The first line of each test case contains two integers n,m with 3 <= n,m <=
11 The following n lines contain m characters, each of the set {"*",
".", "#"}. "*" denotes the place of a deposit,
"." is another grid square of the plan, and "#" is used as
a border and for aligning the grid squares. One can assume that there are
between 1 and 10 places of deposits in a given plan, and the plan is entirely
surrounded by "#".
Output
For each test case print in a single line the lowest number of grid squares involved in a solution that allows access to all diamond deposits. It can be assumed that there is always a solution, and there are at most 20 grid squares needed.
|
Sample Input |
Sample Output |
|
3 11 11 ########### ##.######## #....###### #.*....#### #..*.....## ##....*...# ###....**.# ###.......# ###..*...## ####...#### ########### 3 11 ########### #..*..*...# ########### 11 11 ########### ##.######## #....###### #.*....#### #..*.....## ##....*...# ###....**.# ###....*..# ###..*...## ####...#### ########### |
11 2 13 |
Problem source: Bundeswettbewerb Informatik 2003 (Germany National Olympiad)
Problem submitter: Adrian Kügel
Problem solution: Adrian Kügel
題目描述：
要求挖礦坑道經過指定的地點，且為了礦坑安全，不允許分岔。
題目解法：
窮舉所有節點的所有可能，一、連接到最近的牆壁，二、連到其中一個礦坑。
但是要注意一個礦坑最多只能被另一個礦坑連接。
// 0.400s 不是一個好做法。
#include <string.h>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
struct E {
int to, v;
E(int a, int b):
to(a), v(b) {}
bool operator<(const E &a) const {
if(v != a.v)
return v < a.v;
return to < a.to;
}
};
char g[20][20];
int gv[20][20], n, m, s;
int h[20][20], h2[20];
vector<E> vg[20];
void bfs(int x, int y) {
int nd = gv[x][y], i, j;
int used[20][20] = {};
int tx, ty;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
queue<int> X, Y;
X.push(x), Y.push(y);
used[x][y] = 1;
h[nd][nd] = 0;
h2[nd] = 0xfffffff;
while(!X.empty()) {
x = X.front(), X.pop();
y = Y.front(), Y.pop();
for(i = 0; i < 4; i++) {
tx = x + dx[i], ty = y + dy[i];
if(tx < 0 || ty < 0 || tx >= n || ty >= m)
continue;
if(used[tx][ty])
continue;
if(g[tx][ty] == '#') {
h2[nd] = min(h2[nd], used[x][y]);
} else {
used[tx][ty] = used[x][y]+1;
if(g[tx][ty] == '*')
h[nd][gv[tx][ty]] = used[x][y];
X.push(tx), Y.push(ty);
}
}
}
/*for(i = 0; i < n; i++, puts(""))
for(j = 0; j < m; j++)
printf("%2d", used[i][j]);
puts("**----");*/
}
int ret, used[20], used2[20];
int cut;
void dfs(int idx, int cost) {
if(cost+(s-idx)*1.2 >= ret) return;
if(idx == s) {
ret = min(ret, cost);
return;
}
int i, j, scost;
for(i = 0; i < s; i++) {
if(used[i] == 0) {
for(vector<E>::iterator it = vg[i].begin();
it != vg[i].end(); it++) {
scost = it->v;
if(it->to >= 0) {
if(used[it->to] == 1 && used2[it->to] == 0) {
used[i] = 1;
used2[it->to] = 1;
dfs(idx+1, cost + scost);
used2[it->to] = 0;
used[i] = 0;
}
} else {
used[i] = 1;
dfs(idx+1, cost + scost);
used[i] = 0;
}
}
}
}
}
int main() {
int testcase, i, j;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d", &n, &m);
int idx = 0;
for(i = 0; i < n; i++) {
scanf("%s", &g[i]);
for(j = 0; j < m; j++)
if(g[i][j] == '*')
gv[i][j] = idx++;
}
memset(h, 63, sizeof(h));
for(i = 0; i < n; i++)
for(j = 0; j < m; j++)
if(g[i][j] == '*')
bfs(i, j);
for(i = 0; i < idx; i++)
vg[i].clear();
for(i = 0; i < idx; i++) {
//printf("%d : ", h2[i]);
for(j = 0; j < idx; j++)
vg[i].push_back(E(j, h[i][j]));
vg[i].push_back(E(-1, h2[i]));
sort(vg[i].begin(), vg[i].end());
// printf("%d ", h[i][j]);
}
s = idx;
ret = 20;
dfs(0, 0);
printf("%d\n", ret);
}
return 0;
}
/*
3
11 11
###########
##.########
#....######
#.*....####
#..*.....##
##....*...#
###....**.#
###.......#
###..*...##
####...####
###########
3 11
###########
#..*..*...#
###########
11 11
###########
##.########
#....######
#.*....####
#..*.....##
##....*...#
###....**.#
###....*..#
###..*...##
####...####
###########
*/