POJ 3945 - Traveling Cube

http://poj.org/problem?id=3945

概要

w * d のグリッドがあり，各マスには色が塗られている．

• 赤，緑，青，シアン，マゼンタ，黄のマスがそれぞれ1つずつ
• それ以外のマスは白か黒

というように塗られている．

各面に色が塗られたサイコロがあり，初期状態は

• 上側は赤
• 下側はシアン
• 北側は緑
• 南側はマゼンタ
• 東側は青
• 西側は黄

となっている．

6色の辿る順番が与えられるので，この順番にサイコロを転がして移動させたときの，最小ステップ数を答える． ただし，最後まで辿り着けないときは「unreachable」と出力する．

• 白のマスは何度通っても構わない
• 黒のマスは通ることができない
• その他6色のマスはいずれもそのマスと同じ色の面が上になるときにしか移動できず，また1度しか通れない

制約

• 1 <= w, h <= 30

解法

がんばって BFS する．

サイコロの状態はある2面が決まれば1通りに決まるので，状態数は高々 30*30*6*6*6 しかない． ただ，状態としては3面持っていたほうがやりやすいと思う．

  1 #include <iostream>
  2 #include <queue>
  3 #include <algorithm>
  4 using namespace std;
  5 static const int INF = 10000000;
  6 
  7 struct cube
  8 {
  9   int x, y, t, n, e, i;
 10   cube(int a, int b, int c, int d, int e_, int f)
 11     : x(a), y(b), t(c), n(d), e(e_), i(f)
 12   {}
 13   int top() const { return t; }
 14   int bottom() const { return t^1; }
 15   int north() const { return n; }
 16   int south() const { return n^1; }
 17   int east() const { return e; }
 18   int west() const { return e^1; }
 19   char color() const
 20   {
 21     static const char tbl[] = "rcgmby";
 22     return tbl[top()];
 23   }
 24 };
 25 
 26 int bfs(const vector<string>& grid, const string& route, int x, int y)
 27 {
 28   const int H = grid.size();
 29   const int W = grid[0].size();
 30   static int dist[30][30][6][6][6];
 31   for (int i = 0; i < H; i++) {
 32     for (int j = 0; j < W; j++) {
 33       for (int t = 0; t < 6; t++) {
 34         for (int n = 0; n < 6; n++) {
 35           fill_n(dist[i][j][t][n], 6, INF);
 36         }
 37       }
 38     }
 39   }
 40   queue<cube> q;
 41   q.push(cube(x, y, 0, 2, 4, 0));
 42   dist[x][y][0][2][0] = 0;
 43   int ans = INF;
 44   while (!q.empty()) {
 45     const cube c = q.front();
 46     q.pop();
 47     const int dd = dist[c.x][c.y][c.t][c.n][c.i];
 48     for (int d = 0; d < 4; d++) {
 49       cube cc(c);
 50       static const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
 51       cc.x += dx[d];
 52       cc.y += dy[d];
 53       if (0 <= cc.x && cc.x < H && 0 <= cc.y && cc.y < W && grid[cc.x][cc.y] != 'k') {
 54         switch (d) {
 55           case 0: // north
 56             cc.n = c.top();
 57             cc.t = c.south();
 58             break;
 59           case 1: // south
 60             cc.n = c.bottom();
 61             cc.t = c.north();
 62             break;
 63           case 2: // west
 64             cc.e = c.bottom();
 65             cc.t = c.east();
 66             break;
 67           case 3: // east
 68             cc.e = c.top();
 69             cc.t = c.west();
 70             break;
 71         }
 72         if (grid[cc.x][cc.y] != 'w') {
 73           if (grid[cc.x][cc.y] == route[cc.i] && grid[cc.x][cc.y] == cc.color()) {
 74             ++cc.i;
 75             if (cc.i == 6) {
 76               ans = min(ans, dd+1);
 77             } else {
 78               int& ddd = dist[cc.x][cc.y][cc.t][cc.n][cc.i];
 79               if (dd+1 < ddd) {
 80                 ddd = dd+1;
 81                 q.push(cc);
 82               }
 83             }
 84           }
 85         } else {
 86           int& ddd = dist[cc.x][cc.y][cc.t][cc.n][cc.i];
 87           if (dd+1 < ddd) {
 88             ddd = dd+1;
 89             q.push(cc);
 90           }
 91         }
 92       }
 93     }
 94   }
 95   return ans;
 96 }
 97 
 98 int main()
 99 {
100   ios::sync_with_stdio(false);
101   int W, H;
102   while (cin >> W >> H && W != 0) {
103     vector<string> grid(H);
104     int x, y;
105     for (int i = 0; i < H; i++) {
106       cin >> grid[i];
107       for (int j = 0; j < W; j++) {
108         if (grid[i][j] == '#') {
109           x = i;
110           y = j;
111           grid[i][j] = 'w';
112         }
113       }
114     }
115     string route;
116     cin >> route;
117 
118     const int ans = bfs(grid, route, x, y);
119     if (ans == INF) {
120       cout << "unreachable" << endl;
121     } else {
122       cout << ans << endl;
123     }
124   }
125   return 0;
126 }