HA30_Races(6)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Grid {
private:
    int n, m;
    vector<vector<char> > grid;
    vector<vector<int> > visited;

    // Смещения для движений: вверх, вниз, влево, вправо
    int dx[4];
    int dy[4];

    int sx, sy;
    int tx, ty;

public:
    Grid(int n_rows, int m_cols) {
        n = n_rows;
        m = m_cols;
        grid.resize(n, vector<char>(m));
        visited.resize(n, vector<int>(m, -1));

        // Инициализация смещений
        dx[0] = -1; dy[0] = 0;
        dx[1] = 1;  dy[1] = 0;
        dx[2] = 0;  dy[2] = -1;
        dx[3] = 0;  dy[3] = 1;

        sx = sy = tx = ty = -1;
    }

    void read_grid() {
        for (int i = 0; i < n; ++i) {
            string line;
            cin >> line;
            for (int j = 0; j < m; ++j) {
                grid[i][j] = line[j];
                if (grid[i][j] == 'S') {
                    sx = i;
                    sy = j;
                } else if (grid[i][j] == 'T') {
                    tx = i;
                    ty = j;
                }
            }
        }
    }

    bool is_valid(int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < m;
    }

    int bfs() {
        if (sx == -1 || tx == -1) {
            return -1;
        }

        queue<pair<int, int> > q;
        q.push(make_pair(sx, sy));
        visited[sx][sy] = 0;

        while (!q.empty()) {
            pair<int, int> current = q.front();
            q.pop();
            int x = current.first;
            int y = current.second;
            int presses = visited[x][y];

            if (x == tx && y == ty) {
                return presses;
            }

            for (int dir = 0; dir < 4; ++dir) {
                int nx = x;
                int ny = y;
                int steps = 0;

                // Движение в направлении dir до стены или препятствия
                while (true) {
                    int next_x = nx + dx[dir];
                    int next_y = ny + dy[dir];

                    if (!is_valid(next_x, next_y) || grid[next_x][next_y] == '#') {
                        break;
                    }
                    nx = next_x;
                    ny = next_y;
                    steps++;
                }

                if (steps == 0) {
                    continue; // Машинка не может двигаться в этом направлении
                }

                // Отскок на половину пройденного пути (целочисленное деление)
                int bounce_steps = steps / 2;

                // Позиция после отскока
                int final_x = nx - dx[dir] * bounce_steps;
                int final_y = ny - dy[dir] * bounce_steps;

                if (visited[final_x][final_y] == -1 || visited[final_x][final_y] > presses + 1) {
                    visited[final_x][final_y] = presses + 1;
                    q.push(make_pair(final_x, final_y));
                }
            }
        }

        return -1;
    }
};

int main() {
    int n, m;
    cin >> n >> m;

    Grid grid(n, m);
    grid.read_grid();

    int result = grid.bfs();

    cout << result << endl;

    return 0;
}