算法分析

暴力 $\operatorname{bfs}$ 的复杂度为 $O(H^2W^2)$

考虑优化：

注意到，使用同一个字母的传送器两次显然是没用的，所以如果你使用了一次传送器，接下来你就不能再使用那个字母了！
时间复杂度可以降为 $O(HW)$

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using P = pair<int, int>;

const int INF = 1001001001;
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, 1, 0, -1};

int main() {
    int h, w;
    cin >> h >> w;

    vector<string> s(h);
    rep(i, h) cin >> s[i];

    vector dist(h, vector(w, INF));
    queue<P> q;
    rep(i, h)rep(j, w) {
        if (s[i][j] == 'S') {
            q.emplace(i, j);
            dist[i][j] = 0;
        }
    }
    vector<vector<P>> warps(256);
    rep(i, h)rep(j, w) warps[s[i][j]].emplace_back(i, j);

    while (q.size()) {
        auto [i, j] = q.front(); q.pop();
        if (s[i][j] == 'G') {
            cout << dist[i][j] << '\n';
            return 0;
        }
        rep(v, 4) {
            int ni = i+di[v], nj = j+dj[v];
            if (ni < 0 or ni >= h or nj < 0 or nj >= w) continue;
            if (s[ni][nj] == '#') continue;
            if (dist[ni][nj] != INF) continue;
            dist[ni][nj] = dist[i][j]+1;
            q.emplace(ni, nj);
        }

        if (islower(s[i][j])) {
            for (auto [ni, nj] : warps[s[i][j]]) {
                if (dist[ni][nj] != INF) continue;
                dist[ni][nj] = dist[i][j]+1;
                q.emplace(ni, nj);
            }
            warps[s[i][j]].clear();
        }
    }

    puts("-1");

    return 0;
}