http://acm.hdu.edu.cn/showproblem.php?pid=1044
先用優先隊列算出項鏈、入口、出口之間的相互關系(效率很差 我好像用了多次優先隊列 別人的可能一次廣搜就把所有的關系都算出來了吧 搜索是遇*不搜居然忘了 真粗心)
然后在一次DFS枚舉所有情況就完了。。。
#include <iostream>
#include <queue>
#include <string>
#define MAXN 51
using namespace std;
string mat[MAXN];
int rel[ 12 ][ 12 ];
int nec[ 12 ], ans;
int summ, z;
int W, H, LT, n;
typedef struct {
int i, j;
}Point;
Point pp[ 12 ];
int m;
typedef struct point {
int i , j;
int step;
friend bool operator < (point a , point b) {
return a.step > b.step;
}
}point;
int step[MAXN][MAXN];
int mov[ 4 ][ 2 ] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void BFS (int a, int b) {
int i , j;
point p , q;
for(i = 0;i < H; ++ i) {
for(j = 0;j < W; ++ j) {
step[ i ][ j ] = 10000000;
}
}
priority_queue <point> Q;
p.i = pp[ a ].i, p.j = pp[ a ].j , p.step = 0;
mat[ p.i ][ p.j ] = 0;
Q.push (p);
while (!Q.empty ()) {
q = Q.top ();
Q.pop ();
if (q.i == pp[ b ].i && q.j == pp[ b ].j) {
//cout << "To get from " << a << " to " << b << " takes " << q.step << " knight moves." << endl;
rel[ a ][ b ] = rel[ b ][ a ] = q.step;
return ;
}
for (i = 0; i < 4; ++ i) {
p.i = q.i + mov[ i ][ 0 ];
p.j = q.j + mov[ i ][ 1 ];
if(mat[ p.i ][ p.j ] == '*') continue;
p.step = q.step + 1;
if (p.i >= 0 && p.i < H && p.j >= 0 && p.j < W) {
if (step[ p.i ][ p.j ] > p.step) {
step[ p.i ][ p.j ] = p.step;
Q.push (p);
}
}
}
}
rel[ a ][ b ] = rel[ b ][ a ] = -1;
}
void print() {
for(int i = 0; i < m ; ++ i) {
for(int j = 0; j < m; ++ j) {
if(i == j) continue;
cout << i << " " << j << " " << rel[ i ][ j ] << endl;
}
}
}
void init() {
m = 0;
int ei, ej, i, j;
for(i = 0; i < H; ++ i) {
for(j = 0; j < W; ++ j) {
if(mat[ i ][ j ] == '@') {
pp[ 0 ].i = i;
pp[ 0 ].j = j;
++ m;
}
else if(mat[ i ][ j ] == '<') {
ei = i;
ej = j;
}
else if(mat[ i ][ j ] >= 'A' && mat[ i ][ j ] <= 'J') {
int c = mat[ i ][ j ] - 'A' + 1;
pp[ c ].i = i;
pp[ c ].j = j;
++ m;
}
}
}
pp[ m ].i = ei;
pp[ m ].j = ej;
++ m;
for(i = 0; i < m ; ++ i) {
for(j = i + 1; j < m; ++ j) {
BFS (i, j);
}
}
//print();
}
bool vist[12];
void dfs (int lay, int ss, int step) {
if (ans == summ || step >= LT || rel[ lay ][m - 1] == -1) {
return;
}
if (step + rel[ lay ][m - 1] <= LT && ss > ans) {
ans = ss;
}
for (int i = 1; i <= n; ++ i) {
if (!vist[ i ] && rel[ lay ][ i ] != -1) {
vist[ i ] = true;
dfs (i, ss + nec[ i ], step + rel[ lay ][ i ]);
vist[i] = false;
}
}
}
void result() {
ans = -1;
if(rel[ 0 ][m - 1] > LT || rel[ 0 ][m - 1] == -1) {
puts("Impossible");
return ;
}
memset(vist, false, sizeof(vist));
vist[ 0 ] = true;
dfs (0, 0, 0);
if(ans > 0)
printf("The best score is %d.\n", ans);
else
puts("Impossible");
}
int main() {
int test, i, z = 1;
cin >> test;
while(test --) {
scanf("%d %d %d %d", &W, &H, <, &n);
summ = 0;
for(i = 1; i <= n; ++ i) {
scanf("%d", &nec[ i ]);
summ += nec[ i ];
}
nec[ 0 ] = nec[n + 1] = 0;
for(i = 0; i < H; ++ i) {
//cin >> mat[ i ];
while(getline(cin, mat[ i ], '\n')) {
if(mat[ i ] != "") break;
}
}
printf("Case %d:\n", z ++);
init();
result();
if(test) cout << endl;
}
return 0;
}