2025年推箱子

推箱子推箱子游戏相信大家都不陌生 在本题中 你将控制一个人把 1 个箱子到目的地 给定一张 N 行 M 列的地图 用字符 表示空地 字符 表示墙 字符 S 表示人的起始位置 字符 B 表示箱子的起始位置 字符 T 表示箱子的目标位置 求一种移动方案

大家好,我是讯享网,很高兴认识大家。

推箱子游戏相信大家都不陌生,在本题中,你将控制一个人把1个箱子到目的地。

给定一张N行M列的地图,用字符”.”表示空地,字符”#”表示墙,字符”S”表示人的起始位置,字符”B”表示箱子的起始位置,字符”T”表示箱子的目标位置。

求一种移动方案,使箱子移动的次数最少,在此基础上再让人移动的总步数最少。

方案中使用大写的“EWSN”(东西南北)表示箱子的移动,使用小写的“ewsn”(东西南北)表示人的移动。

推箱子.jpg

对于每个测试用例,第一行包括两个整数N,M。

接下来N行,每行包括M个字符,用以描绘整个N行M列的地图。


讯享网

当样例为N=0,M=0时,表示输入终止,且该样例无需处理。

第二行输入一个字符串,表示推箱子的总体移动过程,若无解,则输出”Impossible.”。

每个测试用例输出结束后输出一个空行。

若有多条路线满足题目要求,则按照N、S、W、E的顺序优先选择箱子的移动方向(即先上下推,再左右推)。

在此前提下,再按照n、s、w、e的顺序优先选择人的移动方向(即先上下动,再左右动)。

输入样例: 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 

讯享网
讯享网#include<bits/stdc++.h> #define pii pair<int,int> using namespace std; const int N = 25; char g[N][N]; pii d[N][N][4]; vector<int> path[N][N][4]; vector<int> seq;//临时存放路径的变量 int n, m; //上下左右 int dx[4] = { 
   -1, 1, 0, 0}; int dy[4] = { 
   0, 0, -1, 1}; typedef struct { 
    int x, y, dir; } state; bool v_man[N][N], v_box[N][N][4]; state pre_box[N][N][4]; state st; int pre_man[N][N]; pii man, box; inline void read() { 
    for (int i = 0; i < n; i++) scanf("%s", g[i]); } inline void init() { 
    memset(d, 0x3f, sizeof(d)); 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}; } } bool check(int x, int y) { 
    return x >= 0 && x < n && y >= 0 && y < m && g[x][y] != '#'; } bool bfs_man(pii sta, pii fin, pii forbid) { 
    seq.clear(); memset(v_man, false, sizeof(v_man)); memset(pre_man, -1, sizeof(pre_man)); queue<pii > q; q.push(sta); v_man[sta.first][sta.second] = true; while (!q.empty()) { 
    pii t = q.front(); q.pop(); if (t == fin) { 
   //找到目标位置 int x = t.first, y = t.second; while (pre_man[x][y] != -1) { 
    int dir = pre_man[x][y]; seq.push_back(dir); x -= dx[dir], y -= dy[dir];//往回走 } return true; } for (int i = 0; i < 4; i++) { 
    int x = t.first + dx[i], y = t.second + dy[i]; if (check(x, y) && make_pair(x, y) != forbid && !v_man[x][y]) { 
    v_man[x][y] = true; pre_man[x][y] = i; q.push({ 
   x, y}); } } } return false; } bool bfs_box() { 
    memset(d, 0x3f, sizeof(d)); memset(v_box, false, sizeof(v_box)); queue<state> q; for (int i = 0; i < 4; i++) { 
   //先推一次箱子 int x = box.first, y = box.second; int nx = x + dx[i], ny = y + dy[i];//箱子推到的位置 int px = x - dx[i], py = y - dy[i];//推箱子的位置 if (check(nx, ny) && check(px, py) && bfs_man(man, { 
   px, py}, box)) { 
    q.push({ 
   nx, ny, i}); v_box[nx][ny][i] = true; d[nx][ny][i] = { 
   1, seq.size()}; path[nx][ny][i] = seq;//以方向i将箱子推到nx,ny的人走过的路径的倒序为seq pre_box[nx][ny][i] = { 
   x, y, -1}; } } bool suc = false; pii mn = { 
   1e9, 1e9}; while (!q.empty()) { 
    state t = q.front(); q.pop(); int x = t.x, y = t.y, dir = t.dir;//箱子的位置 int mx = x - dx[dir], my = y - dy[dir];//人的位置 v_box[x][y][dir] = false; if (g[x][y] == 'T') { 
    suc = true; if (d[x][y][dir] < mn) { 
    mn = d[x][y][dir]; st = t; } } for (int i = 0; i < 4; i++) { 
    int nx = x + dx[i], ny = y + dy[i]; int px = x - dx[i], py = y - dy[i]; if (check(nx, ny) && check(px, py) && bfs_man({ 
   mx, my}, { 
   px, py}, { 
   x, y})) if (d[nx][ny][i] > (pii) { 
   d[x][y][dir].first + 1, d[x][y][dir].second + seq.size()}) { 
    d[nx][ny][i] = { 
   d[x][y][dir].first + 1, d[x][y][dir].second + seq.size()}; path[nx][ny][i] = seq; pre_box[nx][ny][i] = { 
   x, y, dir}; if (!v_box[nx][ny][i]) { 
    v_box[nx][ny][i] = true; q.push({ 
   nx, ny, i}); } } } } return suc; } void solve() { 
    if (!bfs_box()) { 
    printf("Impossible.\n\n"); return; } char ops[] = "nswe"; string res; while (st.dir != -1) { 
    res += ops[st.dir] - 32; for (auto dir:path[st.x][st.y][st.dir])res += ops[dir]; st = pre_box[st.x][st.y][st.dir]; } reverse(res.begin(), res.end()); cout << res << endl << endl; } int main() { 
    int T = 1; while (scanf("%d%d", &n, &m), n || m) { 
    read(); printf("Maze #%d\n", T++); init(); solve(); } return 0; } 
小讯
上一篇 2025-02-10 12:22
下一篇 2025-04-08 09:05

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/80467.html