迷宫

类似的一道题的题解
参考博客

思路

思路与上面那道类似的题目基本一致，唯一需要注意的是：对当前出队结点$tt$，如果$tt$的四个方向上有传送门，不仅要把$tt$的四个方向中合法方向加入队列，还需要把所有传送门所在的点加入队列，而不是等到出队的点是传送门时再将所有传送门加入队列。具体地，可以参考以下数据

1
4 3
#*E
#.#
#S#
.*.

错误代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
const double eps = 1e-6;
const int N = 1e3 + 10;
int n, m, q;
char g[N][N];
PII start, ed;
vector<PII> v[N][N], space_door; // v[i][j]中存储点(i,j)能通过传送直接到达的点
bool st[N][N];

struct Node
{
    int x, y;
    int step;
    bool operator<(const Node &w) const
    {
        return step > w.step; // bfs的队列优先级: 步数小的优先
    }
};
priority_queue<Node> pq;

int bfs()
{
    memset(st, 0, sizeof st);
    while (pq.size())
        pq.pop();

    pq.push({start.first, start.second, 0});
    st[start.first][start.second] = true;

    while (!pq.empty())
    {
        Node t = pq.top();
        pq.pop();
        if (t.x == ed.first && t.y == ed.second)
            return t.step;

        for (PII i : v[t.x][t.y])
        {
            int a = i.first, b = i.second;
            if (!st[a][b])
            {
                pq.push({a, b, t.step});
                st[a][b] = true;
            }
        }
        for (int i = 0; i < 4; i++)
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a > n - 1 || b < 0 || b > m - 1)
                continue;
            if (st[a][b])
                continue;
            if (g[a][b] == '#')
                continue;

            st[a][b] = true;
            pq.push({a, b, t.step + 1});
        }
    }
    return -1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    for (int t = 1; t <= T; t ++)
    {
        space_door.clear();
        cin >> n >> m;
        for (int i = 0; i < n; i++)
        {
            cin >> g[i];
        }

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (g[i][j] == 'S')
                    start.first = i, start.second = j;
                if (g[i][j] == 'E')
                    ed.first = i, ed.second = j;
                if (g[i][j] == '*')
                    space_door.push_back({i, j});
                v[i][j].clear();
            }
        }
        for (int i = 0; i < space_door.size(); i++)
        {
            for (int j = i + 1; j < space_door.size(); j++)
            {
                PII a = space_door[i], b = space_door[j];
                v[a.first][a.second].push_back({b.first, b.second});
                v[b.first][b.second].push_back({a.first, a.second});
            }
        }
        cout << "Case #" << t <<  ": " << bfs() << '\n';
    }
    return 0;
}

正确代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
const double eps = 1e-6;
const int N = 1e3 + 10;
int n, m, q;
char g[N][N];
PII start, ed;
vector<PII> v[N][N], space_door; // v[i][j]中存储点(i,j)能通过传送直接到达的点
bool st[N][N];

struct Node
{
    int x, y;
    int step;
    bool operator<(const Node &w) const
    {
        return step > w.step; // bfs的队列优先级: 步数小的优先
    }
};
priority_queue<Node> pq;

int bfs()
{
    memset(st, 0, sizeof st);
    while (!pq.empty())
        pq.pop();

    pq.push({start.first, start.second, 0});
    st[start.first][start.second] = true;

    while (!pq.empty())
    {
        Node t = pq.top();
        pq.pop();
        if (t.x == ed.first && t.y == ed.second)
            return t.step;
        
        for (int i = 0; i < 4; i++)
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a > n - 1 || b < 0 || b > m - 1)
                continue;
            if (st[a][b])
                continue;
            if (g[a][b] == '#')
                continue;

            if (g[a][b] == '*')
            {
                for (PII j: space_door)
                {
                    pq.push({j.first, j.second, t.step + 1});
                    st[j.first][j.second] = true;
                }
            }
            else
            {
                st[a][b] = true;
                pq.push({a, b, t.step + 1});
            }
        }
    }
    return -1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    for (int t = 1; t <= T; t ++)
    {
        space_door.clear();
        cin >> n >> m;
        for (int i = 0; i < n; i++)
        {
            cin >> g[i];
        }

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (g[i][j] == 'S')
                    start.first = i, start.second = j;
                if (g[i][j] == 'E')
                    ed.first = i, ed.second = j;
                if (g[i][j] == '*')
                    space_door.push_back({i, j});
            }
        }
        // for (int i = 0; i < space_door.size(); i++)
        // {
        //     for (int j = i + 1; j < space_door.size(); j++)
        //     {
        //         PII a = space_door[i], b = space_door[j];
        //         v[a.first][a.second].push_back({b.first, b.second});
        //         v[b.first][b.second].push_back({a.first, a.second});
        //     }
        // }
        cout << "Case #" << t <<  ": " << bfs() << '\n';
    }
    return 0;
}