//方便以后回顾错误
//http://acm.hdu.edu.cn/showproblem.php?pid=1044
//题意 给定起点、终点和图上的宝藏的权值，问 在规定的步数内能否从起点走到终点；若能走到，可携带宝藏的总价值最大是多少
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 #include<queue>
5 #include<vector>
6 using namespace std;
7
8 const int dx[] = {-1, 1, 0, 0};
9 const int dy[] = { 0, 0,-1, 1};
10
11 int n, m, time, p;// 1<=n,m<=50 1<=l<=1000000 1<=p<=10
12 char G[55][55];// 图
13 int vis[55][55];
14 int dis[15][15];// 两个点之间的距离（编号）
15 int bin[15];// 存宝藏的价值
16
17 typedef pair<int, int> Pair;
18 vector<Pair > v;// 存起点、终点和宝藏的坐标
19 int len;// v的大小
20
21 struct node {
22 int x, y, step;
23 node(int x,int y,int step):x(x),y(y),step(step){}
24 };
25
26 bool can_go(node b) {
27 if(b.x < 0 || b.x >= n || b.y < 0 || b.y >= m || G[b.x][b.y] == '*' || vis[b.x][b.y]) return false;
28 return true;
29 }
30
31 void bfs(int s, int e) {
32 dis[s][e] = dis[e][s] = 1000005;/* 这一步没加，改了半个下午bug。因为可能s达不到e 所以要先赋值为最大步长，这里bfs不是返回距离，以前都是返回距离或者bool，换个写法没考虑到这细节。。。*/
33 memset(vis, 0, sizeof(vis));
34 node a(v[s].first, v[s].second, 0);
35 vis[v[s].first][v[s].second] = 1;
36 queue<node> q;
37 q.push(a);
38 while(!q.empty()) {
39 a = q.front();
40 q.pop();
41 if(a.x == v[e].first && a.y == v[e].second) {
42 dis[s][e] = dis[e][s] = a.step;
43 break;
44 }
45 for(int i = 0; i != 4; ++i) {
46 node b(a.x+dx[i], a.y+dy[i], a.step+1);
47 if(can_go(b)) {
48 q.push(b);
49 vis[b.x][b.y] = 1;
50 }
51 }
52 }
53 }
54
55 int maxn;
56 int all_value;
57 int vis2[15];
58 void dfs(int cur, int step, int sum) {
59 if(step > time) return;
60 if(maxn == all_value) return;//剪枝 所有宝藏都找到了。。。
61 if(cur == len-1) {
62 //printf("-----
");
63 if(sum > maxn) maxn = sum;
64 return;
65 }
66 for(int i = 0; i != len; ++i) {
67 if(!vis2[i] && cur != i) {
68 //printf("----
");
69 vis2[i] = 1;
70 dfs(i, step+dis[cur][i], sum+bin[i]);
71 vis2[i] = 0;
72 }
73 }
74 }
75
76 int main() {
77 int T, cnt = 0;
78 scanf("%d", &T);
79 while(T--) {
80 scanf("%d%d%d%d", &m, &n, &time, &p);
81 memset(bin, 0, sizeof(bin));
82 all_value = 0;
83 for(int i = 1; i <= p; ++i) {
84 scanf("%d", &bin[i]);
85 all_value += bin[i];
86 }
87 bin[0] = bin[p+1] = 0;
88 len = 2+p;
89 //Pair init_p = make_pair(-1, -1);
90 v.clear();
91 v.resize(50);
92 for(int i = 0; i != n; ++i) {
93 scanf("%s", G[i]);
94 for(int j = 0; j != m; ++j) {
95 if(G[i][j] == '@') { v[0] = make_pair(i, j); }
96 else if(G[i][j] == '<') { v[len-1] = make_pair(i, j); }
97 else if(G[i][j] >= 'A' && G[i][j] <= 'J') { v[G[i][j]-'A'+1] = make_pair(i, j); }
98 }
99 }
100 //printf("%d
", v.size());
101 for(int i = 0; i != len-1; ++i) {
102 for(int j = i+1; j != len; ++j) {
103 bfs(i, j);// bfs所有结点(起点、宝藏、终点) 两两之间的最短距离
104 //printf("%d
", dis[i][j]);
105 }
106 //printf("%d %d
", v[i].first, v[i].second);
107 }
108 //printf("------
");
109 maxn = -1;
110 memset(vis2, 0, sizeof(vis2));
111 vis2[0] = 1;
112 dfs(0, 0, 0);
113 if(cnt) printf("
");
114 printf("Case %d:
", ++cnt);
115 if(maxn == -1) printf("Impossible
");
116 else printf("The best score is %d.
", maxn);
117 }
118 return 0;
119 }