POJ 2384 - Harder Sokoban Problem

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

概要

N * N のマス目が与えられ，各マスは空白か壁のいずれかである．

プレイヤーは箱を押してゴール地点まで運ぶ． プレイヤーは1ステップで上下左右に動くことができる． 動いた先のマスに箱がある場合，箱を押して進む． ただしプレイヤーも箱も壁のマスには移動できない．

ゴール地点の位置が与えられたとき，ある箱とプレイヤーの初期位置から箱をゴールまで移動させるのに必要な最小ステップ数の最大値を答える．

制約

解法

(箱の位置, プレイヤーの位置) の状態数は 25^4 = 390625 しかない．

ゴールに箱を置いて，その上下左右それぞれにプレイヤーを置いて箱を「ひっぱる」ように BFS して最短経路を求め，その最大値を求める． ただし，箱を一度も押せない場合は無効なので 0 と答えるようにする．

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 struct state { int i, j, k, l, d; };
 8 
 9 int main()
10 {
11   int N;
12   cin >> N;
13   vector<string> grid(N);
14   int gi = -100, gj = -100;
15   for (int i = 0; i < N; i++) {
16     cin >> grid[i];
17     for (int j = 0; j < N; j++) {
18       if (grid[i][j] == '*') {
19         gi = i;
20         gj = j;
21         grid[i][j] = '.';
22       }
23     }
24   }
25 
26   static const int INF = 10000000;
27   static int dist[25][25][25][25];
28   for (int i = 0; i < N; i++) {
29     for (int j = 0; j < N; j++) {
30       for (int k = 0; k < N; k++) {
31         fill_n(dist[i][j][k], N, INF);
32       }
33     }
34   }
35   queue<state> q;
36   state init;
37   init.i = gi;
38   init.j = gj;
39   init.d = 0;
40   static const int di[] = {-1, 1, 0, 0}, dj[] = {0, 0, -1, 1};
41   for (int d = 0; d < 4; d++) {
42     init.k = gi - di[d];
43     init.l = gj - dj[d];
44     if (0 <= init.k && init.k < N && 0 <= init.l && init.l < N && grid[init.k][init.l] != '#') {
45       dist[init.i][init.j][init.k][init.l] = 0;
46       q.push(init);
47     }
48   }
49 
50   int ans = 0;
51   bool valid = false;
52   while (!q.empty()) {
53     const state s = q.front();
54     q.pop();
55     ans = max(ans, s.d);
56 
57     state t;
58     t.d = s.d + 1;
59     for (int d = 0; d < 4; d++) {
60       const int k = s.k + di[d];
61       const int l = s.l + dj[d];
62       if (0 <= k && k < N && 0 <= l && l < N && grid[k][l] != '#' && !(k == s.i && l == s.j)) {
63         if (s.k - di[d] == s.i && s.l - dj[d] == s.j) {
64           // 'push'
65           valid = true;
66           t.i = s.k;
67           t.j = s.l;
68           t.k = k;
69           t.l = l;
70           if (t.d < dist[t.i][t.j][t.k][t.l]) {
71             dist[t.i][t.j][t.k][t.l] = t.d;
72             q.push(t);
73           }
74         }
75         t.i = s.i;
76         t.j = s.j;
77         t.k = k;
78         t.l = l;
79         if (t.d < dist[t.i][t.j][t.k][t.l]) {
80           dist[t.i][t.j][t.k][t.l] = t.d;
81           q.push(t);
82         }
83       }
84     }
85   }
86   cout << (valid ? ans : 0) << endl;
87 
88   return 0;
89 }
poj/2384.cc