1 #include <iostream>
 2 #include <queue>
 3 #include <cstring>
 4 #include <cstdio>
 5 using namespace std;
 6 
 7 typedef struct node_st {
 8     int x, y, t;
 9     int key;
10     node_st() {}
11     node_st(int xx, int yy, int tt, int kk) {
12         x = xx; y = yy; t = tt; key = kk;
13     }
14 } node_st;
15 
16 char map[25][25];
17 char visit[1<<10][25][25];
18 int direct[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
19 int n, m, time;
20 
21 int bfs(int bx, int by) {
22     int x, y, key, t;
23     int i, tmp;
24     queue<node_st> que;
25     node_st node;
26 
27     memset(visit, 0, sizeof(visit));
28     visit[bx][by][0] = 1;
29     que.push(node_st(bx,by,0,0));
30 
31     while ( !que.empty() ) {
32         node = que.front();
33         if (node.t >= time)
34             return -1;
35         if (map[node.x][node.y] == ‘^‘)
36             return node.t;
37         que.pop();
38         t = node.t + 1;
39         for (i=0; i<4; ++i) {
40             x = node.x + direct[i][0];
41             y = node.y + direct[i][1];
42             if (x<0 || x>=n || y<0 || y>=m)
43                 continue;
44             if (map[x][y]>=‘a‘ && map[x][y]<=‘j‘)
45                 key = node.key | (1<<(map[x][y]-‘a‘));
46             else
47                 key = node.key;
48             if (visit[key][x][y] || map[x][y]==‘*‘)
49                 continue;
50             if (map[x][y]>=‘A‘ && map[x][y]<=‘J‘) {
51                 tmp = (1<<(map[x][y]-‘A‘)) & key;
52                 if ( !tmp )
53                     continue;
54             }
55             que.push(node_st(x,y,t,key));
56             visit[key][x][y] = 1;
57         }
58     }
59 
60     return -1;
61 }
62 
63 int main() {
64     int bx, by;
65     int i, j;
66 
67     while (scanf("%d %d %d", &n, &m, &time) != EOF) {
68         for (i=0; i<n; ++i) {
69             scanf("%s", map[i]);
70             for (j=0; j<m; ++j) {
71                 if (map[i][j] == ‘@‘) {
72                     bx = i;
73                     by = j;
74                 }
75             }
76         }
77         i = bfs(bx, by);
78         printf("%d\n", i);
79     }
80 
81     return 0;
82 }