#include #define rep(i,n) for(int i = 0; i < (n); i++) using namespace std; typedef long long ll; // g <- pair < v , cost > template < class T > vector< T > bfs(vector>> &graph, int s) { T INF = numeric_limits< T >::max(); vector dist(graph.size(), INF); queue> q; q.push({dist[s] = T(0), s}); while(!q.empty()){ auto [uc, ui] = q.front(); q.pop(); if(uc != dist[ui]) continue; for(auto [vi, vc] : graph[ui]) if(dist[vi] > uc + vc) q.push({dist[vi] = uc + vc, vi}); } return dist; } int main(){ cin.tie(0); ios::sync_with_stdio(0); int W,H; cin >> W >> H; vector C(H); rep(i,H) cin >> C[i]; vector> S, T; int di[] = {0, 1, 0, -1}; int dj[] = {1, 0, -1, 0}; auto f = [&](vector> &V, char X) { rep(i,H)rep(j,W) if(C[i][j] == '.') { queue> q; q.push({i, j}); V.push_back({i, j}); C[i][j] = X; while(!q.empty()) { auto [ci, cj] = q.front(); q.pop(); rep(d,4) { int ni = ci + di[d], nj = cj + dj[d]; if(0 <= ni && ni < H && 0 <= nj && nj < W && C[ni][nj] == '.') { C[ni][nj] = X; V.push_back({ni, nj}); q.push({ni, nj}); } } } return; } }; f(S, 'S'); f(T, 'T'); vector>> G(H * W + 2); auto h = [&](int i, int j){ return i * W + j; }; rep(i,H)rep(j,W)rep(d,4) { int ni = i + di[d], nj = j + dj[d]; if(0 <= ni && ni < H && 0 <= nj && nj < W) { G[h(i, j)].push_back({h(ni, nj), 1}); } } int s = H * W, t = s + 1; for(auto [i, j] : S) G[s].push_back({h(i, j), 0}); for(auto [i, j] : T) G[h(i, j)].push_back({t, 0}); cout << bfs(G, s)[t] - 1 << endl; }