题目描述

blablabla

样例

blablabla

算法1

我是真的不想写搜索. 太难调了

先看题目要求的优先级

1.箱子移动步骤最少

2.人移动步骤最少

3.先上下,再左右

所以应对题目要求,我们先要使得箱子移动步骤最少

我们就把箱子广搜呗(期间保证人也可以移动到推箱子的位置)

比如 箱子从 (x, y) 到 (x + d[i][0], y + d[i][1])
那么人就必须能从 当前位置(a, b) 到 ((x - d[i][0], y - d[i][1])

这样箱子移动就最少

然后是人移动最少, 所以人位置的转移也爆搜呗

最后是先上下,再左右, 我们的d[4][2] 就先顺序写呗

d[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

你以为这就完了?

尽管我们保证了箱子路径最短,

但是箱子路径长度相同的情况下, 我们人的移动只是局部最优(就是确定箱子路径(长度相同, 路径不同)的情况下)

所以我们应当把所有的箱子路径最短的情况答案全部求出来, 排序输出第一个

细节见代码

参考文献

C++ 代码

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define fi first
#define se second
using namespace std;
typedef pair<int, int> PII;

int ma[21][21], n, m, _;
int d[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
char der[5] = "nswe";

int read()
{
    char c = getchar();
    while (c != '#' && c != '.' && c != 'T' && c != 'B' && c != 'S') c = getchar();

    if (c == '#') return 1;
    if (c == '.') return 0;
    if (c == 'T') return 2;
    if (c == 'B') return 3;
    return 4;
}

queue<pair<PII, string>> q;
set<PII> st;

string bfs_man(PII a, PII b, PII box)
{
    queue<pair<PII, string>>().swap(q);
    set<PII>().swap(st);
    q.push({ a, "" }); st.insert(a);

    if (ma[b.fi][b.se] == 1 || ma[a.fi][a.se] == 1) return "1";

    while (!q.empty())
    {
        string s = q.front().se;
        PII cur = q.front().fi; q.pop();

        if (cur == b) return s;

        rep(i, 0, 3)
        {
            int x = cur.fi + d[i][0], y = cur.se + d[i][1];
            if (x > n || x < 1 || y > m || y < 1) continue;
            if (ma[x][y] == 1 || (x == box.fi && y == box.se)) continue;
            if (!st.count({ x, y })) 
                q.push({ {x, y}, s + der[i] }), st.insert({ x, y });
        }
    }
    return "1";
}

bool cmp(string& a, string& b)
{
    if (a.size() != b.size()) return a.size() < b.size();

    int i = 0;
    while (i < a.size() && i < b.size() && a[i] == b[i]) ++i;

    rep (j, 0, 3)
        if (a[i] == der[j] || a[i] == char(der[j] ^ 32)) return true;
        else if (b[i] == der[j] || b[i] == char(der[j] ^ 32)) return false;
}

queue<pair<pair<PII, PII>, string>> qu;
set <pair<PII, PII>> stt;

string bfs_box(PII b, PII r, PII t)
{
    queue<pair<pair<PII, PII>, string>>().swap(qu);
    set <pair<PII, PII>>().swap(stt);
    qu.push({ {b, r}, "" });

    vector<string> ve;

    while (!qu.empty())
    {
        b = qu.front().fi.fi, r = qu.front().fi.se;
        string s = qu.front().se; qu.pop();

        if (b == t) {ve.emplace_back(s); continue;}

        if (!ve.empty()) continue;

        rep(i, 0, 3)
        {
            int x = b.fi + d[i][0], y = b.se + d[i][1];
            int rx = b.fi - d[i][0], ry = b.se - d[i][1];
            if (x > n || x < 1 || y > m || y < 1) continue;
            if (ma[x][y] == 1) continue;
            string pe = bfs_man(r, { rx, ry }, b);
            if (pe == "1") continue;

            string cur = s + pe + char(der[i] ^ 32);
            if (!stt.count({ {x, y}, b }))
                qu.push({ {{x, y}, b}, cur }), stt.insert({ {x, y}, b });
        }
    }

    if (ve.empty()) return "";

    sort(ve.begin(), ve.end(), cmp);

    return ve[0];
}

int main()
{
    int bx, by, tx, ty, sx, sy;
    while (scanf("%d%d", &n, &m), n + m)
    {
        printf("Maze #%d\n", ++_);
        rep(i, 1, n)
            rep(j, 1, m)
        {
            ma[i][j] = read();
            if (ma[i][j] == 2) tx = i, ty = j;
            else if (ma[i][j] == 3) bx = i, by = j;
            else if (ma[i][j] == 4) sx = i, sy = j;
        }

        string ans = bfs_box({ bx, by }, { sx, sy }, { tx, ty });
        if (ans == "") puts("Impossible.\n");
        else printf("%s\n\n", ans.c_str());
    }
    return 0;
}