python/TangDou/AcWing/BFS/ECNU1224.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 210;

struct Node {
    int x, y; // 坐标
    int dis;  // 距离
    bool const operator<(const Node &b) const {
        return dis > b.dis;
    }
};
// 问：优先队列默认是大顶堆，如果想距离小的在前怎么办呢？
// 答：重载小于操作符。对比距离，谁的距离大谁就小。

char g[N][N];       // 地图
int sx, sy, tx, ty; // 起点坐标与终点坐标

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int n, m; // 代表迷宫的高和宽

void bfs() {
    priority_queue<Node> q; // 在priority_queue中，优先队列默认是大顶堆
    Node st{sx, sy, 0};
    g[sx][sy] = '#';
    q.push(st);

    while (q.size()) {
        Node u = q.top();
        q.pop();
        // 若已找到，则退出
        if (u.x == tx && u.y == ty) {
            cout << u.dis << endl;
            return;
        }
        for (int i = 0; i < 4; i++) {
            int x = u.x + dx[i];
            int y = u.y + dy[i];
            Node t = {x, y, 0};

            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] != '#') {
                if (g[x][y] == 'X')
                    t.dis = u.dis + 2;
                else
                    t.dis = u.dis + 1;
                // 走过就覆盖掉
                g[t.x][t.y] = '#';
                // 新结点入队列
                q.push(t);
            }
        }
    }
    // 没有结果，输出不可能到达
    printf("impossible\n");
}
int main() {
    while (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') sx = i, sy = j;
                if (g[i][j] == 'T') tx = i, ty = j;
            }
        bfs();
    }
    return 0;
}