思路：很明显的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;
}

#include<stdio.h>

#include<queue>

using namespace std;

char map[1005][1005];

int vis[1005][1005] = {0};

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

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

struct p

{

int x,y,ans;

}b,t;

queue

q;

int n,m;

int m1,m2;

void bfs()

{

vis[b.x][b.y] = 1;

while(!q.empty())

{

b = q.front();

q.pop();

if(b.x == m1 && b.y == m2)

{

printf("宿主可成功逃脱，最快逃脱步数为 %d 步

\n",b.ans);

return;

}

for(int i=0;i<4;i++)

{

int nex = b.x + dx[i];

int ney = b.y + dy[i];

if(nex >=1 && nex <=n && ney >=1 && ney

<=m && vis[nex][ney] == 0 && map[nex]

[ney] != '*')

{

vis[nex][ney] = 1;

t.x = nex,t.y = ney,t.ans = b.ans+1;

q.push(t);

}

}

}

printf("宿主任务失败，宣告死亡\n");

}

int main()

{

scanf("%d %d",&n,&m);

for(int i=1;i<=n;i++)

{

for(int j=1;j<=m;j++)

{

scanf(" %c",&map[i][j]);

if(map[i][j] == 'T')

{

m1 = i;

m2 = j;

}

if(map[i][j] == 'S')

{

b.x = i;

b.y = j;

b.ans = 0;

}

}

}

q.push(b);

bfs();

return 0;

}