【正经题解】Maze II

使用 $BFS$ （广度优先搜索）进行迷宫的遍历，从左上角开始。
使用队列存储当前位置的信息（坐标和步数）。
判断当前位置是否为传送门，如果是，则将传送门的位置加入队列，同时将标志变为 $false$ ，表示不再继续传送。
遍历上、下、左、右四个方向，如果下一步是空地，则将下一步的坐标和步数加入队列。
当队列为空时，表示无法到达右下角，输出 $-1$ 。
如果到达右下角，输出最短路径的步数。

#include<bits/stdc++.h>
using namespace std;

int n, m;
int a[45][45];
int fx[] = {1, 0, -1, 0};
int fy[] = {0, 1, 0, -1};
struct Node {
    int x, y, d;
};

// 传送门的坐标
struct node {
    int x, y;
};

vector<node> v;

int main() {
    cin >> n >> m;
    char c;
    
    // 读入迷宫信息
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> c;
            if (c != '#') a[i][j] = 1; // 空地标记为1
            if (c == '$') v.push_back({i, j}); // 传送门坐标记录
        }
    }
    
    queue<Node> q;
    q.push({1, 1, 1}); // 将起点加入队列
    bool flag = true; // 传送门标志
    
    while (!q.empty()) {
        Node t = q.front();
        q.pop();

        if (t.x == n && t.y == m) {
            cout << t.d; // 到达终点，输出最短路径步数
            return 0;
        }

        if (flag) {
            // 如果当前位置是传送门，设置flag为false，将传送门位置加入队列
            for (auto i : v) {
                if (i.x == t.x && i.y == t.y) {
                    flag = false;
                    break;
                }
            }
            if (!flag) {
                for (auto i : v) {
                    q.push({i.x, i.y, t.d});
                }
            }
        }

        // 向四个方向移动
        for (int i = 0; i < 4; i++) {
            int nx = t.x + fx[i];
            int ny = t.y + fy[i];
            
            // 如果下一步是空地，标记为已经访问，并将下一步的坐标和步数加入队列
            if (a[nx][ny]) {
                a[nx][ny] = 0;
                q.push({nx, ny, t.d + 1});
            }
        }
    }
    cout << "-1"; // 队列为空，表示无法到达终点
    return 0;
}