奶牛们去一个 � × � N×M 玉米迷宫， 2 ≤ � ≤ 300 , 2 ≤ � ≤ 300 2≤N≤300,2≤M≤300。 迷宫里有一些传送装置，可以将奶牛从一点到另一点进行瞬间转移。这些装置可以双向使用。 如果一头奶牛处在这个装置的起点或者终点，这头奶牛就必须使用这个装置。 玉米迷宫除了唯一的一个出口都被玉米包围。 迷宫中的每个元素都由以下项目中的一项组成： 玉米，# 表示，这些格子是不可以通过的。 草地，. 表示，可以简单的通过。 传送装置，每一对大写字母 � A 到 � Z 表示。 出口，= 表示。 起点， @ 表示 奶牛能在一格草地上可能存在的四个相邻的格子移动，花费 1 1 个单位时间。从装置的一个结点到另一个结点不花时间。c++

代码如下：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int N = 310;

int n, m;
char g[N][N];
bool st[N][N];
int dist[N][N];
vector<pair<int,int>> portals[26];

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

struct Node {
    int x, y, d;
};

int bfs(int sx, int sy) {
    memset(dist, -1, sizeof dist);
    memset(st, 0, sizeof st);
    queue<Node> q;
    q.push({sx, sy, 0});
    dist[sx][sy] = 0;
    while(q.size()) {
        auto t = q.front();
        q.pop();
        int x = t.x, y = t.y, d = t.d;
        if(g[x][y] == '=') return d;
        for(int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m || g[a][b] == '#') continue;
            if(g[a][b] >= 'A' && g[a][b] <= 'Z') {
                auto& vec = portals[g[a][b] - 'A'];
                for(auto& p : vec) {
                    int aa = p.first, bb = p.second;
                    if(aa == a && bb == b) continue;
                    if(dist[aa][bb] != -1) continue;
                    dist[aa][bb] = d + 1;
                    q.push({aa, bb, d + 1});
                }
            } else {
                if(dist[a][b] != -1) continue;
                dist[a][b] = d + 1;
                q.push({a, b, d + 1});
            }
        }
    }
    return -1;
}

int main() {
    cin >> n >> m;
    int sx, sy;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> g[i][j];
            if(g[i][j] == '@') {
                sx = i, sy = j;
            } else if(g[i][j] >= 'A' && g[i][j] <= 'Z') {
                portals[g[i][j] - 'A'].push_back({i, j});
            }
        }
    }
    cout << bfs(sx, sy) << endl;
    return 0;
}

思路：

我们可以先把所有的传送门的位置存下来，也就是记录下每个大写字母出现的位置。然后使用 BFS，每次扩展到一个位置，判断是否是出口，如果是出口就返回距离。如果当前位置是传送门，那么就可以直接跳到与其对应的传送门所在的位置。注意要处理好重复走的问题，我们可以使用 dist 数组记录每个位置是否被访问过。

时间复杂度：

每个位置最多被访问一次，时间复杂度为 O(NM)。