//【C6-7】走出迷宫的最少步数2 #include <iostream> using namespace std; char a[105][105]; int d[105][105]; int n,m; int sx,sy,ex,ey; int dx[5]={0,-1,0,1,0}; int dy[5]={0,0,1,0,-1}; void dfs(int x,int y,int step) { if (x==ex&&y==ey) { if (step<d[ex][ey]) { d[ex][ey] = step; } return; } for (int i=1;i<=4;i++) { int nx=x+dx[i]; int ny=y+dy[i]; if (nx>=0&&nx<n&&ny>=0&&ny<m&&a[nx][ny]!='#'&&step+1<d[nx][ny]) { d[nx][ny]=step+1; dfs(nx,ny,step+1); } } } int main() { cin>>n>>m; for(int i=0;i<n;i++) { cin>>a[i]; for (int j=0;j<m;j++) { d[i][j]=10000; if (a[i][j]=='S'){ sx=i; sy=j; } else if(a[i][j]=='T') { ex=i; ey=j; } } } d[sx][sy]=0; dfs(sx,sy,0); cout<<d[ex][ey]<<endl; return 0; }