UVa 589 - Pushing Boxes

发表于 分类于 ， ， Disqus：

链接

传送门

题意

给出\(r \times c (1 \leq r,c \leq 20)\)的矩阵，代表推箱子的地图，输出把箱子推到指定地点的方案，要求推的次数最少，推的次数相同时，人走动的次数尽量少。

思路

可以将推的次数和走动次数转化为一个权值，将人的位置和箱子的位置作为状态，进行bfs，记录每个状态到达的最小权值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int maxn = 25;
const char dirs[2][5] = {"news", "NEWS"};
const int dir[4][2] = {{-1, 0}, {0, 1}, {0, -1}, {1, 0}};
int r, c;
int vis[maxn][maxn][maxn][maxn];
char path[maxn][maxn][maxn][maxn];
char a[maxn][maxn], ans[maxn * maxn * maxn * maxn];
struct Pos {
  int x, y;
};
struct Status {
  Pos s, b;
  int w;
  Status() {}
  Status(Pos& s, Pos& b, int w): s(s), b(b), w(w) {}
  bool operator < (const Status& rhs) const {
    return w > rhs.w;
  }
};
priority_queue<Status> q;

int main() {
  int t = 0;
  while (~scanf("%d%d", &r, &c) && (r || c)) {
    Status k;
    for (int i = 1; i <= r; ++i) {
      scanf("%s", a[i] + 1);
      for (int j = 1; j <= c; ++j) {
        if (a[i][j] == 'S') {
          k.s.x = i, k.s.y = j;
        } else if (a[i][j] == 'B') {
          k.b.x = i, k.b.y = j;
        }
      }
    }
    memset(path, 0, sizeof path);
    memset(vis, 0x3f, sizeof vis);
    vis[k.s.x][k.s.y][k.b.x][k.b.y] = k.w = 0;
    q = priority_queue<Status>();
    q.push(k);
    bool flag = true;
    printf("Maze #%d\n", ++t);
    while (!q.empty()) {
      k = q.top();
      q.pop();
      if (a[k.b.x][k.b.y] == 'T') {
        flag = false;
        int len = 0;
        while (vis[k.s.x][k.s.y][k.b.x][k.b.y] != 0) {
          char& c = path[k.s.x][k.s.y][k.b.x][k.b.y];
          ans[len++] = path[k.s.x][k.s.y][k.b.x][k.b.y];
          for (int i = 0; i < 4; ++i) {
            if (tolower(c) == dirs[0][i]) {
              k.s.x -= dir[i][0], k.s.y -= dir[i][1];
              if (isupper(c)) {
                k.b.x -= dir[i][0], k.b.y -= dir[i][1];
              }
              break;
            }
          }
        }
        while (len--) {
          putchar(ans[len]);
        }
        break;
      }
      for (int i = 0; i < 4; ++i) {
        Pos ns = k.s;
        ns.x += dir[i][0], ns.y += dir[i][1];
        if (ns.x == k.b.x && ns.y == k.b.y) {
          Pos nb = k.b;
          nb.x += dir[i][0], nb.y += dir[i][1];
          if (nb.x >= 1 && nb.y >= 1 && nb.x <= r && nb.y <= c && a[ns.x][ns.y] != '#' && k.w + 100000 < vis[ns.x][ns.y][nb.x][nb.y]) {
            q.push(Status(ns, nb, k.w + 100000));
            vis[ns.x][ns.y][nb.x][nb.y] = k.w + 100000;
            path[ns.x][ns.y][nb.x][nb.y] = dirs[1][i];
          }
        } else if (ns.x >= 1 && ns.y >= 1 && ns.x <= r && ns.y <= c && a[ns.x][ns.y] != '#' && k.w + 1 < vis[ns.x][ns.y][k.b.x][k.b.y]) {
          q.push(Status(ns, k.b, k.w + 1));
          vis[ns.x][ns.y][k.b.x][k.b.y] = k.w + 1;
          path[ns.x][ns.y][k.b.x][k.b.y] = dirs[0][i];
        }
      }
    }
    puts(flag ? "Impossible.\n" : "\n");
  }
  return 0;
}
相关文章