题目描述
推箱子游戏相信大家都不陌生,在本题中,你将控制一个人把1个箱子到目的地。
给定一张N行M列的地图,用字符”.”表示空地,字符”#”表示墙,字符”S”表示人的起始位置,字符”B”表示箱子的起始位置,字符”T”表示箱子的目标位置。
求一种移动方案,使箱子移动的次数最少,在此基础上再让人移动的总步数最少。
方案中使用大写的“EWSN”(东西南北)表示箱子的移动,使用小写的“ewsn”(东西南北)表示人的移动。
样例
输入样例:
1 7
SB....T
1 7
SB..#.T
7 11
###########
#T##......#
#.#.#..####
#....B....#
#.######..#
#.....S...#
###########
8 4
....
.##.
.#..
.#..
.#.B
.##S
....
###T
0 0
输出样例:
Maze #1
EEEEE
Maze #2
Impossible.
Maze #3
eennwwWWWWeeeeeesswwwwwwwnNN
Maze #4
swwwnnnnnneeesssSSS
算法1
(bfs套bfs) $O(n)$
代码中dx
表示的含义,比如箱子应该往上走一个, 那么人的位置应该在下面所以坐标x = 1, y = 0,依次枚举四个方向。
还有最后在输出人的方向的时候,需要^1
因为,方向ops[] = "nwse"
中 第一个是箱子往上走, 那么人应该往下,所以需要^1
时间复杂度
参考文献
C++ 代码
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 25;
struct Node{
int x, y, dir;
};
int n, m;
char g[N][N];
Node pre[N][N][4];
vector<int> path[N][N][4];
bool st[N][N][4], used[N][N];//st表示箱子的搜索中的点是否被遍历过, used表是人走过的点是否被遍历过
PII dist[N][N][4];
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};//依次表示 下, 上, 右, 左
int pre_man[N][N];
bool check(int x, int y){
return x >= 0 && x < n && y >= 0 && y < m && g[x][y] != '#';
}
int bfs_man(PII start, PII end, PII box, vector<int> &seq){
memset(used, false, sizeof used);
memset(pre_man, -1, sizeof pre_man);
queue<PII> q;
q.push(start);
used[start.first][start.second] = true;
used[box.first][box.second] = true;
while (q.size()){
auto t = q.front(); q.pop();
if (t == end){
seq.clear();
int x = t.first, y = t.second;
while (pre_man[x][y] != -1){
int dir = pre_man[x][y] ^ 1;
seq.push_back(dir);
x += dx[dir], y += dy[dir];
}
return seq.size();
}
for (int ii = 0; ii < 4; ii ++ ){
int i = ii ^ 1;
int x = t.first, y = t.second;
int a = x + dx[i], b = y + dy[i];
if (check(a, b) && !used[a][b]){
used[a][b] = true;
pre_man[a][b] = i;
q.push({a, b});
}
}
}
return -1;
}
bool bfs_box(PII man, PII box, Node &end){
memset(st, false, sizeof st);
queue<Node> q;
for (int i = 0; i < 4; i ++ ){
int x = box.first, y = box.second;
int a = x + dx[i], b = y + dy[i];
int j = x - dx[i], k = y - dy[i];
vector<int> seq;
if (check(a, b) && check(j, k) && bfs_man(man, {a, b}, box, seq) != -1){
st[j][k][i] = true;
q.push({j, k, i});
dist[j][k][i] = {1, seq.size()};
path[j][k][i] = seq;
pre[j][k][i] = {x, y, -1};
}
}
bool success = false;
PII man_d = {1e9, 1e9};
while (q.size()){
auto t = q.front();
q.pop();
if (g[t.x][t.y] == 'T'){
success = true;
if (dist[t.x][t.y][t.dir] < man_d){
man_d = dist[t.x][t.y][t.dir];
end = t;
}
}
for (int i = 0; i < 4; i ++ ){
int a = t.x + dx[i], b = t.y + dy[i];
int j = t.x - dx[i], k = t.y - dy[i];
if (check(a, b) && check(j, k)){
vector<int> seq;
auto &p = dist[j][k][i];
int distance = bfs_man({t.x + dx[t.dir], t.y + dy[t.dir]}, {a, b}, {t.x, t.y}, seq);
if (distance != -1){
PII td = {dist[t.x][t.y][t.dir].first + 1, dist[t.x][t.y][t.dir].second + distance};//前面一个表示箱子移动次数,得 + 1, 第二个表示人的移动距离,得+distance
if (!st[j][k][i]){
st[j][k][i] = true;
q.push({j, k, i});
path[j][k][i] = seq;
pre[j][k][i] = t;
p = td;
}else if(p > td){
p = td;
path[j][k][i] = seq;
pre[j][k][i] = t;
}
}
}
}
}
return success;
}
int main(){
int T = 1;
while (cin >> n >> m, n || m ){
for (int i = 0; i < n; i ++) cin >> g[i];
printf("Maze #%d\n", T ++);
PII man, box;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if (g[i][j] == 'S') man = {i, j};
else if (g[i][j] == 'B') box = {i, j};
Node end;
if (!bfs_box(man, box, end)) puts("Impossible.");
else{
char ops[] = "nswe";
string res;
while (end.dir != -1){//因为将起点的方向置为-1了,所以倒着循环到方向为-1,即到达起点。
res += ops[end.dir] - 32;
for (auto dir : path[end.x][end.y][end.dir]) res += ops[dir];
end = pre[end.x][end.y][end.dir];
}
reverse(res.begin(), res.end());
cout << res << endl;
}
puts("");
}
return 0;
}