|
|
思路：
这题就是平常玩的那种推箱子的游戏。不过简化了一下，只是推一个箱子而已。
用 bfs 来做，搜索树里面的节点，也就是状态，可以定义为：
1. 箱子的坐标
2. 上一次推完之后，人要走多少步才能到达箱子的上、下、左、右侧。如果到达不了，值则为无穷大。
这样，状态转移的时候。
就首先看是否能向某个方向推。如果能的话，就推一下。
然后对人进行一次 bfs ，看下此时到达箱子的各个侧要走多少步。
就可以生成一个新的状态了。
判重的处理做得很简单：
对于同一个坐标，不可能存在一个状态，它的“人要走多少步才能到达箱子的上、下、左、右侧”这四个值都比另外一个状态大。
代码写得很乱，调试得真痛苦，足足4K多啊，看了下 status 里面，发现有的牛人代码还是写得很短的，佩服佩服！
后来又看了标程，发现太飘逸了，看不懂。。
 #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define DATA_SIZE 24
#define QUEUE_SIZE 65536
#define INFINITE 1000000
#define dbp printf
  struct node  {
 int y, x, dir, dis[4], pushes, walks;
struct node *next, *hash_next;
 };
struct queue {
struct node arr[QUEUE_SIZE];
int qh, qt;
};
struct node box, man, off[4] = {
  {-1, 0}, {1, 0}, {0, -1}, {0, 1}
};
int H, W;
char map[DATA_SIZE][DATA_SIZE];
char lower[] = "nswe", upper[] = "NSWE";
__inline int input()
{
int i, j;
scanf("%d%d", &H, &W);
if (!H)
return 0;
for (i = 0; i < H; i++) {
scanf("%s", map[i]);
for (j = 0; j < W; j++) {
if (map[i][j] == 'B') {
box.x = j;
box.y = i;
map[i][j] = '.';
} else if (map[i][j] == 'S') {
man.x = j;
man.y = i;
map[i][j] = '.';
 }
}
}
return 1;
}
__inline int can_go(int y, int x)
{
return x >= 0 && x < W && y >= 0 && y < H && map[y][x] != '#';
}
__inline void move_man(struct node *b, struct node *m, struct node *rec[])
{
int mask, got, i;
static struct queue q;
static char visited[DATA_SIZE][DATA_SIZE];
mask = 0;
for (i = 0; i < 4; i++)
if (can_go(b->y + off[i].y, b->x + off[i].x))
mask |= 1 << i;
#define PUSH(_y, _x, _walks, _next, _dir) \
if (_y == b->y && _x == b->x) { \
got |= 1 << _dir; \
b->dis[_dir] = _walks; \
if (rec) \
rec[_dir] = m; \
} else if (!visited[_y][_x]) { \
q.arr[q.qt].y = _y; \
q.arr[q.qt].x = _x; \
q.arr[q.qt].walks = _walks; \
q.arr[q.qt].next = _next; \
q.arr[q.qt].dir = _dir; \
visited[_y][_x] = 1; \
q.qt++; \
}
q.qh = q.qt = 0;
for (i = 0; i < 4; i++)
b->dis[i] = INFINITE;
memset(visited, 0, sizeof(visited));
PUSH(m->y, m->x, 0, NULL, 0);
got = 0;
while (q.qh != q.qt && got != mask) {
m = &q.arr[q.qh++];
for (i = 0; i < 4; i++) {
if (!can_go(m->y + off[i].y, m->x + off[i].x))
continue;
PUSH(m->y + off[i].y, m->x + off[i].x,
m->walks + 1, m, i
);
}
}
#undef PUSH
}
__inline struct node *reverse(struct node *t)
{
struct node *p, *n;
p = NULL;
while (t) {
n = t->next;
t->next = p;
p = t;
t = n;
}
return p;
}
__inline int hash_insert(struct node **p, struct node *b)
{
int i;
struct node *h;
for (h = *p; h; h = h->hash_next) {
for (i = 0; i < 4; i++)
if (h->dis[i] > b->dis[i])
break;
if (i == 4)
return 0;
}
b->hash_next = *p;
*p = b;
return 1;
}
__inline void dump_walks(struct node *b, struct node *m, int d)
{
struct node *rec[4];
move_man(b, m, rec);
//dbp("(%d,%d) -> (%d,%d) %c\n", m->x, m->y, b->x, b->y, lower[d]);
for (b = reverse(rec[d])->next; b; b = b->next)
putchar(lower[b->dir]);
putchar(upper[d]);
}
__inline void solve()
{
struct node *b, *n, *best;
static struct queue q;
static struct node *hash[DATA_SIZE][DATA_SIZE];
int i;
memset(hash, 0, sizeof(hash));
#define PUSH(_y, _x, _m, _pushes, _walks, _next, _dir) \
{ \
n = &q.arr[q.qt]; \
n->y = _y; \
n->x = _x; \
n->pushes = _pushes; \
n->walks = _walks; \
n->next = _next; \
n->dir = _dir; \
move_man(n, _m, NULL); \
if (map[_y][_x] == 'T') { \
if (!best || n->walks < best->walks) { \
best = n; \
q.qt++; \
} \
} else if (hash_insert(&hash[_y][_x], n)) { \
q.qt++; \
} \
}
best = NULL;
q.qh = q.qt = 0;
PUSH(box.y, box.x, &man, 0, 0, NULL, 0);
while (q.qt != q.qh) {
b = &q.arr[q.qh++];
if (best && b->pushes > best->pushes)
break;
for (i = 0; i < 4; i++) {
if (!can_go(b->y + off[i].y, b->x + off[i].x))
continue;
if (b->dis[i] == INFINITE)
continue;
PUSH(b->y + off[i].y, b->x + off[i].x,
b, b->pushes + 1, b->dis[i] + b->walks,
b, i
);
}
}
if (!best) {
printf("Impossible.\n\n");
return ;
}
//dbp("%d pushes %d walks\n", best->pushes, best->walks);
b = reverse(best);
dump_walks(b, &man, b->next->dir);
n = b;
for (b = b->next; b->next; b = b->next) {
dump_walks(b, n, b->next->dir);
n = b;
}
printf("\n\n");
}
int main()
{
int i;
freopen("e:\\test\\in.txt", "r", stdin);
for (i = 1; input(); i++) {
printf("Maze #%d\n", i);
solve();
}
return 0;
}
|