小火龙最近在研究机器人，他想看看自己的机器人够不够智能，于是他将机器人放在一个 $n \times m$ 的迷宫中，看看机器人能不能在最短的时间内到达目的地，可是小火龙不知道最短的时间是多少，现在请你帮他算算机器人到达目的地的最短时间是多少？

输入格式

输入数据第一行两个整数 $n$ 和 $m$。

接下来 $n$ 行，每行 $m$ 个元素，表示迷宫的每个方格。

'S' 表示机器人的出发点,

'T' 表示目的地，

'#' 表示该方格不能通过

'.'表示可以通过

输出格式

输出一个整数，表示机器人到达目的地的最短时间，如果机器人不能到达目的地，输出 -1。

$n$和 $m$ 的范围就算是在[10,500]。

（是不是必须写宽捜……）

#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
int n,m,sx,sy,ex,ey,ans=1e9;
bool b[101][501]; 
char a[101][501];
void dfs(int x,int y,int k){
    if(x==ex&&y==ey){
        ans=min(ans,k);
        return;
    }
    for(int i=0;i<4;i++){
        int nx=x+dx[i],ny=y+dy[i];
        if(a[nx][ny]=='#'||nx<0||ny<0||nx>n||ny>m||b[nx][ny]) continue;
        else{
        	b[nx][ny]=1;
            dfs(nx,ny,k+1);
            b[nx][ny]=0;
        }
    }
    return;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]=='S'){
                sx=i,sy=j;
                b[i][j]=1;
            }
            if(a[i][j]=='T'){
                ex=i,ey=j;
            }
        }
    }
    dfs(sx,sy,0);
    cout<<ans<<"\n";
    return 0;
}