题解[广度优先搜索]

简简单单

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y;
char mp[105][105];
bool vis[105][105];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
struct node{int x,y,st;};
bool check(int x,int y){return x>=1 and x<=n and y>=1 and y<=m and mp[x][y]!='#' and !vis[x][y];}
void bfs(int sx,int sy){
    queue<node>q;
    q.push({sx,sy,0});
    vis[sx][sy]=1;
    while(!q.empty()){
        node f=q.front();
        q.pop();
        if(mp[f.x][f.y]=='T'){
            cout << f.st;
            return;
        }
        for(int i=0;i<4;i++){
            int nx=f.x+dx[i];
            int ny=f.y+dy[i];
            if(check(nx,ny)){
                q.push({nx,ny,f.st+1});
                vis[nx][ny]=1;
            }
        }
    }
    cout << -1;
}
int main(){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> mp[i][j];
            if(mp[i][j]=='S'){
                x=i;
                y=j;
            }
        }
    }
    bfs(x,y);
}