1 #include <iostream> 2 #include <queue> 3 #include <cstring> 4 using namespace std; 5  6 int n , m , t; 7 const int size = 25; 8 char mp[size][size]; 9 bool vis[size][size][1<<11];10 int dir[4][2] = {1,0,-1,0,0,1,0,-1};11 struct node12 {13     int x , y , key , Time;14     node(){};15     node( int u , int v , int z , int w ):x(u),y(v),key(z),Time(w){};16 };17 queue<node>q;18 19 void init( )20 {21     memset( vis , false , sizeof(vis) );22     while( !q.empty() )23     {24         q.pop();25     }26 }27 28 int bfs( int stx , int sty )29 {30     int x , y , key;31     node now;32     q.push( node(stx,sty,0,0) );33     vis[stx][sty][0] = true;34     while( !q.empty() )35     {36         now = q.front();37         q.pop();38         if( now.Time>=t )39         {40             return -1;41         }42         if( mp[now.x][now.y]==‘^‘ )43         {44             return now.Time;45         }46         for( int i = 0 ; i<4 ; i++ )47         {48             x = now.x + dir[i][0];49             y = now.y + dir[i][1];50             key = 0;51             if( x>=0 && x<=n-1 && y>=0 && y<=m-1 && mp[x][y]!=‘*‘ && !vis[x][y][now.key] )52             {53                 if( mp[x][y]>=‘a‘ && mp[x][y]<=‘j‘ )54                 {55                     key |= ( 1<<(mp[x][y]-‘a‘) );56                 }57                 else if( mp[x][y]>=‘A‘ && mp[x][y]<=‘J‘ )58                 {59                     if( !( now.key & ( 1<<( mp[x][y]-‘A‘ ) ) ) )60                     {61                         continue;62                     }63                 }64                 q.push( node( x , y , now.key|key , now.Time+1 ) );65                 vis[x][y][now.key] = true;66             }67         }68     }69     return -1;70 }71 72 int main()73 {74     cin.sync_with_stdio(false);75     int ans , stx , sty;76     while( cin >> n >> m >> t )77     {78         init();79         for( int i = 0 ; i<n ; i++ )80         {81             for( int j = 0 ; j<m ; j++ )82             {83                 cin >> mp[i][j];84                 if( mp[i][j] == ‘@‘ )85                 {86                     stx = i;87                     sty = j;88                 }89             }90         }91         ans = bfs( stx , sty );92         cout << ans << endl;93     }94     return 0;95 }