maze

思路

• 将每个点上的入口到对应出口也看成一条路径, 只不过从这条路径走距离一次+3
• 然后就是普通的bfs，注意队列要使用优先队列, 因为此时的队列不再具备步数的单调性，需要人为保证步数单调性。优先队列元素定义如下，注意优先队列的重载，可以参考《算法笔记》P223

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

代码

#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 = 300 + 10;
int n, m, q;
char g[N][N];
PII start, ed;
vector<PII> v[N][N]; // 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 (g[a][b] != '#')
                pq.push({a, b, t.step + 3});
        }
        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);
    while (cin >> n >> m >> q)
    {
        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] == 'T')
                    ed.first = i, ed.second = j;
                v[i][j].clear();
            }
        }
        while (q--)
        {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            v[x1][y1].push_back({x2, y2});
        }
        cout << bfs() << '\n';
    }
    return 0;
}