UVa 589 - Pushing Boxes

链接

传送门

题意

给出$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;
}

支付宝扫码领红包