思路：很明显的bfs，直接bfs搜就好了，具体代码如下

#include<bits/stdc++.h>
using namespace std;
​
#define int long long
#define endl '\n'
#define FastIO ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
const int N = 1e3 + 9;
​
char mp[N][N];
//四个方向的坐标的变化量 
int mx[4] = {1, 0, -1, 0};
int my[4] = {0, 1, 0, -1};
int vis[N][N];//标记是否访问过 
struct node{
    int x;
    int y;
    int cnt;
};
​
void solve() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m; j ++) {
            cin >> mp[i][j];
        }
    }
    int x = 0, y = 0;
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m; j ++) {
            if(mp[i][j] == 'S') {//寻找地图的起点
                x = i;
                y = j;
                break;
            }
        }
    }
    node st, ne;//st为起点的结点，ne为下一个要遍历的结点 
    st.x = x, st.y = y, st.cnt = 0;
    queue<node> q;
    q.push(st);
    vis[x][y] = 1;
    int ans = 0;
    while(q.size()) {
        node t = q.front();
        q.pop();
        for(int i = 0; i < 4; i ++) {
            int xx = t.x + mx[i], yy = t.y + my[i];
            if(xx < 1 || yy < 1 || xx > n || yy > m || vis[xx][yy] || mp[xx][yy]=='*') {
                continue;
            }
            vis[xx][yy] = 1;
            ne.x = xx, ne.y = yy;
            ne.cnt = t.cnt + 1;
            if(mp[xx][yy] == 'T') {//bfs搜到就是最小值 
                ans = ne.cnt;
                break;
            }
            q.push(ne);
        }
    }
    if(ans) cout << "宿主可成功逃脱，最快逃脱步数为 " << ans << " 步" << endl;
    else cout << "宿主任务失败，宣告死亡" << endl;
}
​
signed main() {
    FastIO;
​
    solve();
    return 0;
}