#include 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 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; }