正宗题解

#include <iostream>
#include <queue>
using namespace std;
char map[105][105];
int vis[105][105],wn,wm,sx,sy;
int dir[4][2]={1,0,-1,0,0,1,0,-1};
int n,m;
struct node{
int x,y,step;
};
queue<node> q;
void bfs(){
while(!q.empty()){
node t=q.front();
q.pop();
if(t.xwn && t.ywm){
cout<<t.step;
return;
}
for(int i=0;i<4;i++){
int nx=t.x+dir[i][0];
int ny=t.y+dir[i][1];
if(nx<0 || nx>=n || ny<0 || ny>=m || map[nx][ny]'#' || vis[nx][ny]){
continue;
}
q.push({nx,ny,t.step+1});
vis[nx][ny]=1;
}
}
cout<<-1;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>map[i][j];
if(map[i][j]'S'){
sx=i;
sy=j;
}
else if(map[i][j]=='T'){
wn=i;
wm=j;
}
}
}
vis[sx][sy]=1;
q.push({sx,sy,0});
bfs();
return 0;
}