1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<queue>
  5 using namespace std;
  6 char map[21][21];
  7 int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
  8 bool hash[21][21][10000];
  9 struct man{
 10     int x,y;
 11     bool key[10];
 12     int t;
 13 };
 14 int si,sj,ei,ej;
 15 int n,m,t;
 16 bool succ;
 17 queue<man>zero;
 18 int main()
 19 {
 20     int i,j,k,ti;
 21     int hh,hh2;
 22     man head,p;
 23     while(scanf("%d%d%d",&n,&m,&t)!=EOF)
 24     {
 25         memset(map,0,sizeof(map));
 26         memset(hash,0,sizeof(hash));
 27         for(i=0;i<n;i++)
 28         {
 29             scanf("%s",map[i]);
 30             for(j=0;j<m;j++)
 31             {
 32                 if(map[i][j]=='@')
 33                 {
 34                     hash[i][j][0]=1;
 35                     si=i;
 36                     sj=j;
 37                     map[i][j]='.';
 38                 }
 39                 if(map[i][j]=='^')
 40                 {
 41                     ei=i;
 42                     ej=j;
 43                     map[i][j]='.';
 44                 }
 45             }
 46         }
 47         head.t=0;
 48         head.x=si;
 49         head.y=sj;
 50         memset(head.key,0,sizeof(head.key));
 51         while(!zero.empty())
 52         zero.pop();
 53         zero.push(head);
 54         succ=0;
 55         ti=99999;
 56         while(!zero.empty())
 57         {
 58             head=zero.front();
 59             zero.pop();
 60             if(head.t==t)
 61             {
 62                 if(head.x==si&&head.y==sj)
 63                 {
 64                     head.t=0;
 65                         hh2=0;
 66                         for(int jj=0;jj<10;jj++)
 67                         {
 68                             if(head.key[jj])
 69                             hh2+=1<<(jj);
 70                         }
 71                         if(hash[si][sj][hh2]==0)
 72                         {
 73                               hash[si][sj][hh2]=1;
 74                             zero.push(head);
 75                         }
 76                     continue;
 77                 }else
 78                 continue;
 79             }
 80             if(head.x==ei&&head.y==ej)
 81             {
 82                 if(head.t<t)
 83                 {
 84                 succ=1;
 85                 ti=head.t;
 86                 break;
 87                 }else
 88             continue;
 89             }
 90             int x,y;
 91             for(i=0;i<4;i++)
 92             {
 93                 x=dir[i][0]+head.x;
 94                 y=dir[i][1]+head.y;
 95                 if(x>=n||y>=m||x<0||y<0||map[x][y]=='*')
 96                 continue;
 97                 hh=0;
 98                 for(int jj=0;jj<10;jj++)
 99                 {
100                     if(head.key[jj])
101                     hh+=1<<(jj);
102                     p.key[jj]=head.key[jj];
103                 }
104              if(map[x][y]=='.'&&hash[x][y][hh]==0)
105                 {
106                     p.x=x;
107                     p.y=y;
108                     p.t=head.t+1;
109                     hash[x][y][hh]=1;
110                     if(p.t<t||(p.t==t&&p.x==si&&p.y==sj))
111                     zero.push(p);
112                 }
113                 if(map[x][y]>='a'&&map[x][y]<='j')
114                 {
115                     if(head.key[map[x][y]-'a']&&hash[x][y][hh]==0)
116                     {
117                         p.x=x;
118                         p.y=y;
119                         p.t=head.t+1;
120                         hash[x][y][hh]=1;
121                         if(p.t<t||(p.t==t&&p.x==si&&p.y==sj))
122                         zero.push(p);
123                     }
124                     else if(!head.key[map[x][y]-'a']&&hash[x][y][hh+1<<(map[x][y]-'a')]==0)
125                     {
126                         p.key[map[x][y]-'a']=1;
127                            hh+=1<<(map[x][y]-'a');
128                         hash[x][y][hh]=1;
129                         p.x=x;
130                         p.y=y;
131                         p.t=head.t+1;
132                         if(p.t<t||(p.t==t&&p.x==si&&p.y==sj))
133                         zero.push(p);
134                     }
135                 }
136                 if(map[x][y]>='A'&&map[x][y]<='J'&&hash[x][y][hh]==0&&head.key[map[x][y]-'A'])
137                 {
138                     hash[x][y][hh]=1;
139                     p.x=x;
140                     p.y=y;
141                     p.t=head.t+1;
142                     if(p.t<t||(p.t==t&&p.x==si&&p.y==sj))
143                     zero.push(p);
144                 }
145             }
146         }
147         if(succ)
148         printf("%d\n",ti);
149         else
150         printf("-1\n");
151     }
152 }
153                     
154