hdu 1429胜利大逃亡(续)

//hash判重
//好孩子；
//hdu1429利用二进制的&和|运算：
#include<iostream>
#include<queue>
using namespace std;
const int T = 22;
char g[T][T];
int vis[T][T][1030],n,m,t,ans;
int dir[4][2]={0,1,1,0,0,-1,-1,0};

struct point{
    int x;
    int y;
    int step;
    int key;
};
point s;

void inset(){
    for(int i=0;i<n;i++){
        cin>>g[i];
        for(int j=0;j<m;j++){
            if(g[i][j]=='@'){
                s.x=i;
                s.y=j;
                s.key=0;
                s.step=0;
            }
        }
    }
}


void bfs(){
    queue<point>  Q;
    point tp;
    ans=-1;
    memset(vis,0,sizeof(vis));
    vis[s.x][s.y][s.key]=1;
    Q.push(s);
    while(!Q.empty()){
         tp=Q.front();Q.pop();
         for(int k=0;k<4;k++){
             s=tp;
             s.x=tp.x+dir[k][0];
             s.y=tp.y+dir[k][1];
             if(s.x>=0 && s.x<n && s.y>=0 && s.y<m && g[s.x][s.y]!='*' && !vis[s.x][s.y][s.key]){
                 if(g[s.x][s.y]=='.' || g[s.x][s.y]=='@'){
                       vis[s.x][s.y][s.key]=1;
                       s.step+=1;
                       Q.push(s);
                       //cout<<s.x<<" "<<s.y<<endl;
                 }
                 if(g[s.x][s.y]=='^'){
                     if(s.step+1<t) ans=s.step+1;
                     return ;
                 }
                 if(g[s.x][s.y]>='A' && g[s.x][s.y]<='J'){
                      int key=1<<(g[s.x][s.y]-'A');
                      if(s.key & key){
                           vis[s.x][s.y][s.key]=1;
                           s.step+=1;
                           Q.push(s);
                          //cout<<s.x<<" "<<s.y<<endl;
                      }
                 }
                 if(g[s.x][s.y]>='a' && g[s.x][s.y]<='j'){
                       int key=1<<(g[s.x][s.y]-'a');
                       if(!vis[s.x][s.y][s.key|key]){
                            vis[s.x][s.y][s.key|key]=1;
                            s.step+=1;s.key=s.key|key;
                            Q.push(s);
                            //cout<<s.x<<" "<<s.y<<endl;
                       }
                 }
             }
         }
    }
}


int main(){

    while(cin>>n>>m>>t){
        inset();
        bfs();
        cout<<ans<<endl;
    }

    return 0;
}