// 2008アジア地区予選F : Traveling Cube #include #include #include using namespace std; class Node{ public: int x, y, p, d0, d1, c; Node(int x, int y, int p, int d0, int d1, int c) : x(x), y(y), p(p), d0(d0), d1(d1), c(c) {} }; char dx[] = {-1,1,0,0}; char dy[] = {0,0,-1,1}; // サイコロの面の遷移行列 char dice[6][4] = { {5,2,1,4}, {1,1,3,0}, {0,3,2,2}, {2,5,4,1}, {4,4,0,3}, {3,0,5,5} }; char side[] = {1,2,4,5}; // 面番号は,上,左,正面,下,右,背面の順 char dice_color[6] = {'r','y','m','c','b','g'}; char getUpper(int a, int b){ // a(初期状態で上)面が上にある. if(a == 0) return dice_color[0]; // b(初期状態で左)面が上にある. if(b == 0) return dice_color[1]; // a面が下にある if(a == 3) return dice_color[3]; // b面が下にある if(b == 3) return dice_color[4]; return (b-a+6)%6 < 3 ? dice_color[2] : dice_color[5]; } int main(){ ifstream fin("F.in"); int w, d; string path; string mp[30]; while(fin >> w >> d, w){ for(int i=0;i> mp[i]; fin >> path; int sx, sy = -1; for(int i=0;i qu; qu.push(Node(sx,sy,0,0,1,0)); int ans = -1; while(!qu.empty()){ Node nd = qu.front(); qu.pop(); int x = nd.x, y = nd.y, p = nd.p, d0 = nd.d0, d1 = nd.d1, c = nd.c; // 色付きマスをすべて通行した if(p == 6){ ans = c; break; } if(visit[x][y][p][d0][d1]) continue; visit[x][y][p][d0][d1] = true; for(int i=0;i<4;i++){ int nx = x+dx[i], ny = y+dy[i], nd0 = dice[d0][i], nd1 = dice[d1][i]; // フィールド外に出るか,黒マスに移動してしまうとき if(nx<0||d<=nx||ny<0||w<=ny||mp[nx][ny]=='k') continue; // 色つきマスに乗ったとき if(mp[nx][ny]!='w'&&mp[nx][ny]!='#'){ // 上面の色と一致し,かつ今目指している色であるとき if(mp[nx][ny]==getUpper(nd0,nd1)&&mp[nx][ny]==path[p]) qu.push(Node(nx,ny,p+1,nd0,nd1,c+1)); } // 白マスへの移動 else qu.push(Node(nx,ny,p,nd0,nd1,c+1)); } } // ans = -1のままなら到達は無理 ans==-1 ? puts("unreachable") : printf("%d\n", ans); } }