1 #include <stdio.h>
 2 #include <string.h>
 3 #include <queue>
 4 using namespace std;
 5 
 6 int m,n,t;
 7 char graph[25][25];
 8 bool vis[24][24][1<<10];
 9 int dic[4][2] = {-1,0,1,0,0,-1,0,1};
10 struct note{
11 
12     int x,y,state,time;
13 
14 }loc;
15 queue<note>s;
16 /*
17     位运算就是在下面，对于每一个钥匙用二进制的0,1来存
18 */
19 int bfs(int x,int y)
20 {
21     while(!s.empty())
22         s.pop();
23     loc.state = 0;
24     loc.time = 1;
25     loc.x = x;
26     loc.y = y;
27     s.push(loc);
28     while(!s.empty())
29     {
30         note fa,son;
31         fa = s.front();
32         s.pop();
33       //  if(fa.time == t) return -1;
34         for(int i = 0 ; i < 4 ; i++)
35         {
36             son.x = fa.x + dic[ i ][ 0 ];
37             son.y = fa.y + dic[ i ][ 1 ];
38             if(son.x < 1 || son.y < 1|| son.y > n || son.x > m||!vis[son.x][son.y][fa.state]) continue;     //这一行很关键，没有这一行就是MLE
39             if(graph[son.x][son.y] == ‘^‘)
40             {
41                 if(fa.time == t ) return -1;
42                 else return fa.time;
43             }
44             if(graph[son.x][son.y] >=‘a‘&& graph[son.x][son.y] <=‘z‘ &&vis[son.x][son.y][fa.state| (1 <<(graph[son.x][son.y]-‘a‘))])
45             {
46                 son.state = fa.state | (1 <<(graph[son.x][son.y]-‘a‘));
47                 son.time = fa.time+1;
48                 vis[son.x][son.y][son.state] = false;
49                 s.push(son);
50             }
51             else if(graph[son.x][son.y]<=‘Z‘ && graph[son.x][son.y] >=‘A‘ && fa.state & (1 << graph[son.x][son.y]-‘A‘) &&vis[son.x][son.y][fa.state])
52             {
53                 son.state = fa.state;
54                 son.time = fa.time+1;
55                 vis[son.x][son.y][son.state] = false;
56                 s.push(son);
57             }
58            else if(graph[son.x][son.y]==‘.‘||graph[son.x][son.y]==‘@‘&&vis[son.x][son.y][fa.state])
59             {
60                 son.state = fa.state;
61                 son.time = fa.time + 1 ;
62                 vis[son.x][son.y][son.state] = false;
63                 s.push(son);
64             }
65         }
66     }
67     return -1;
68 }
69 
70 int main()
71 {
72  //   freopen("in.txt","r",stdin);
73     int x,y;
74     while(~scanf("%d%d%d",&m,&n,&t))
75     {
76         getchar();        //吃掉一个换行符
77         memset(graph,0,sizeof(graph));
78         memset(vis,true,sizeof(vis));
79         int ans;
80         for(int i = 1 ; i <= m; i++)
81         {
82             for(int j = 1 ; j <= n ; j++)
83             {
84                 scanf("%c",&graph[i][j]);
85                 if(graph[i][j]==‘@‘)
86                     x = i,y = j;
87             }
88             getchar();
89         }
90         ans = bfs(x,y);
91         printf("%d\n",ans);
92     }
93     return 0;
94 }