#include #include #include #include #include #include #include #include using namespace std; typedef pair Pos; // (y,x) typedef int Mask; // |A-Z| bits. 0: close, 1: open typedef pair State; // solve --------------------------------------------------------- int bfs( State start, Pos goal, const vector& mp ) { set visited; vector Q(1, start); for(int steps=0; !Q.empty(); ++steps) { vector nQ; for(int i=0; i!=Q.size(); ++i) { State s = Q[i]; if( visited.count(s) ) continue; visited.insert(s); if( s.first == goal ) return steps; char c = mp[s.first.first][s.first.second]; if( c=='#' ) continue; if( isupper(c) && !(s.second&(1<<(c-'A'))) ) continue; for(int dir=0; dir!=4; ++dir) { static int dy[] = {-1,+1,0,0}; static int dx[] = {0,0,-1,+1}; int y = s.first.first + dy[dir]; int x = s.first.second + dx[dir]; char c = mp[y][x]; Mask m = islower(c) ? s.second ^ (1<<(c-'a')) : s.second; nQ.push_back(State(Pos(y,x),m)); } } Q.swap(nQ); } return -1; } int solve(const vector& mp) { // スタートセルとゴールセルを見つける Pos start, goal; for(int y=0; y!=mp.size(); ++y) for(int x=0; x!=mp[y].size(); ++x) if( mp[y][x]=='@' ) start = Pos(y,x); else if( mp[y][x]=='<' ) goal = Pos(y,x); // BFSで最短パスを探す return bfs( State(start,0), goal, mp ); } // read the input -------------------------------------------------- int main() { int W, H; while(cin >> W >> H, W|H) { assert( 3<=W&&W<=30 ); assert( 3<=H&&H<=30 ); vector mp(H); for(int h=0; h!=H; ++h) cin >> mp[h]; cout << solve(mp) << endl; } }