POJ 3523 - The Morning after Halloween

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

概要

w * h のグリッド上に n 体のロボットの初期位置とそれぞれのゴール地点が与えられる．

1ステップで，同時に各ロボットを4方向に移動させるか全く移動させないという操作ができる． ただし，壁のあるマスへは進めず，また1ステップで2体のロボットの位置をスワップさせるこはできない．

すべてのロボットをゴール地点へ移動させるのに必要な最小のステップ数を答える．

制約

解法

状態数は最大で 256^3 で，壁に囲まれていることや4つ目の制約から実際にはそんなに状態数は無いので，単に BFS してもがんばって定数倍最適化すれば本番のデータセットに対して1分ちょっとで解ける．

しかしこれではオンラインジャッジでは通らないので，A* で解く． このときヒューリスティクスに使うゴールまでの推定距離関数 h には， 各ロボットの位置からそのロボットのゴールまでの距離の最大値を使った． この距離は最初に3回 BFS しておけば求まる．

また，余計な探索候補を入れないようにするために各状態へのステップ数を覚えておきたい． これを int dist[256*256*256] で持つと MLE． short dist[256*256*256] でも AOJ だと MLE するので unsigned char dist[256*256*256] で持った． しかしこれだとオーバーフローする可能性があるので，オーバーフローしたときは map<int,short> に切り替えるようにして MLE を回避した．

以下のコードは POJ 3523 で 3266MS，AOJ 1281 で 1:94 で通ったもの．

  1 #include <cstdio>
  2 #include <map>
  3 #include <queue>
  4 #include <algorithm>
  5 using namespace std;
  6 static const int di[] = {0, -1, 1, 0, 0}, dj[] = {0, 0, 0, -1, 1};
  7 
  8 inline int h(int s, const unsigned short hh[3][256], int N)
  9 {
 10   unsigned short l = 0;
 11   for (int i = 0; i < N; i++) {
 12     l = max(l, hh[i][(s>>(i<<3))&0xff]);
 13   }
 14   return l;
 15 }
 16 
 17 int calc_next(int N, const char grid[16][20], int s, int *a)
 18 {
 19   int next = 0;
 20   for (int i = 0; i < N; i++) {
 21     const int t = (s>>(i<<3))&0xff;
 22     const int k = (t>>4) + di[a[i]];
 23     const int l = (t&0xf) + dj[a[i]];
 24     if (grid[k][l] == '#') {
 25       return -i-1;
 26     }
 27     const int u = (k<<4)|l;
 28     const int v = (s>>(i<<3))&0xff;
 29     for (int j = 0; j < i; j++) {
 30       const int w = (next>>(j<<3))&0xff;
 31       if (u == w) {
 32         return 0;
 33       }
 34       if (u == ((s>>(j<<3))&0xff) && w == v) {
 35         return 0;
 36       }
 37     }
 38     next |= u<<(i<<3);
 39   }
 40   return next;
 41 }
 42 
 43 inline int get(int s, const unsigned char *d1, const map<int,short>& d2)
 44 {
 45   int d = d1[s];
 46   if (d == 255) {
 47     return 1000;
 48   } else if (d == 254) {
 49     return d2.find(s)->second;
 50   } else {
 51     return d;
 52   }
 53 }
 54 
 55 inline void set(int s, unsigned char *d1, map<int,short>& d2, int d)
 56 {
 57   if (d >= 254) {
 58     d1[s] = 254;
 59     d2[s] = d;
 60   } else {
 61     d1[s] = d;
 62   }
 63 }
 64 
 65 int main()
 66 {
 67   char buf[100];
 68   while (fgets(buf, sizeof buf, stdin)) {
 69     int W, H, N;
 70     sscanf(buf, "%d %d %d", &W, &H, &N);
 71     if (N == 0) {
 72       break;
 73     }
 74     char grid[16][20];
 75     int init = 0, final = 0;
 76     for (int i = 0; i < H; i++) {
 77       fgets(grid[i], 20, stdin);
 78       for (int j = 0; j < W; j++) {
 79         if ('a' <= grid[i][j] && grid[i][j] <= 'c') {
 80           init |= (i<<4|j) << ((grid[i][j]-'a')<<3);
 81           grid[i][j] = ' ';
 82         } else if ('A' <= grid[i][j] && grid[i][j] <= 'C') {
 83           final |= (i<<4|j) << ((grid[i][j]-'A')<<3);
 84           grid[i][j] = ' ';
 85         }
 86       }
 87     }
 88     const int A = N >= 0 ? 5 : 1;
 89     const int B = N >= 1 ? 5 : 1;
 90     const int C = N >= 2 ? 5 : 1;
 91 
 92     static unsigned short int hh[3][256];
 93     for (int i = 0; i < N; i++) {
 94       fill_n(hh[i], 256, 1000);
 95       queue<int> q;
 96       q.push((final>>(i<<3))&0xff);
 97       hh[i][(final>>(i<<3))&0xff] = 0;
 98       while (!q.empty()) {
 99         const int s = q.front();
100         const int x = s>>4;
101         const int y = s&0xf;
102         q.pop();
103         for (int d = 1; d < 5; d++) {
104           const int k = x + di[d];
105           const int l = y + dj[d];
106           const int t = (k<<4)|l;
107           if (grid[k][l] != '#' && hh[i][s]+1 < hh[i][t]) {
108             hh[i][t] = hh[i][s]+1;
109             q.push(t);
110           }
111         }
112       }
113     }
114 
115     static unsigned char dist[256*256*256];
116     fill_n(dist, 256*256*256, 255);
117     map<int,short> dist2;
118     dist[init] = 0;
119     priority_queue<pair<short,int> > q;
120     q.push(make_pair(-h(init, hh, N), init));
121     while (!q.empty()) {
122       const int cost = -q.top().first;
123       const int s = q.top().second;
124       q.pop();
125       if (s == final) {
126         printf("%d\n", cost);
127         break;
128       }
129       const int d = cost - h(s, hh, N);
130       const int d2 = get(s, dist, dist2);
131       if (d > d2) {
132         continue;
133       }
134 
135       bool inv[5] = {false, false, false, false, false};
136       int a[3];
137       for (a[0] = 0; a[0] < A; a[0]++) {
138         for (a[1] = 0; a[1] < B; a[1]++) {
139           if (inv[a[1]]) {
140             continue;
141           }
142           for (a[2] = 0; a[2] < C; a[2]++) {
143             const int next = calc_next(N, grid, s, a);
144             if (next == 0) {
145               continue;
146             } else if (next < 0) {
147               if (next == -1) {
148                 goto SKIP_A;
149               } else if (next == -2) {
150                 inv[a[1]] = true;
151                 goto SKIP_B;
152               } else {
153                 continue;
154               }
155             }
156             const int du = get(next, dist, dist2);
157             if (d+1 < du) {
158               set(next, dist, dist2, d+1);
159               q.push(make_pair(-d-1-h(next, hh, N), next));
160             }
161           }
162 SKIP_B:
163           ;
164         }
165 SKIP_A:
166         ;
167       }
168     }
169   }
170   return 0;
171 }
poj/3523.cc