#include #include #include using namespace std; typedef int State; // [mask:8][y:5][x:5] int solve( int W, int H, int start, int goal, char M[] ) { bool visited[1<<18] = {0}; vector Q(1, start); for(int steps=0; !Q.empty(); ++steps) { vector Q2; Q2.swap(Q); for each(State s in Q2) if( !visited[s] ) { visited[s] = true; if( s%1024 == goal ) return steps; char c = M[s%1024]; if( c=='#' || isupper(c) && !(s&(1<<10+c-'A')) ) continue; for(int j=0; j<4; ++j) { static int dir[] = {-1,+1,-32,+32}; char cc = M[s%1024+dir[j]]; Q.push_back( islower(cc) ? s+dir[j] ^ (1<<10+cc-'a') : s+dir[j] ); } } } return -1; } int main() { for(int W,H; scanf("%d %d\n",&W,&H),W|H; ) { // input ---------------------------------------------- char M[32*32]; for(int y=0; y