I.cpp

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

using vi = vector<string>;
using pii = pair<int,int>;
using vpii = vector<pii>;

int movs[4][2] = {
    {0, 1},
    {1, 0},
    {-1, 0},
    {0, -1}
};

vpii finalPath;
bool therePath;
vector <vector<bool>> visited;


bool isValid(vi& grid, int& n, int& m, pii cor) {
    
    if ( cor.first < 0 or cor.first >= n or cor.second < 0 or cor.second >= m) return false;
    if( grid[cor.first][cor.second] == '*' ) return false;
    if( visited[cor.first][cor.second] ) return false;
    
    return true;
}

void getPath(vi& grid, int& n, int& m, vpii& path, pii& target, pii parent) {
    if( parent.first == target.first and parent.second == target.second) {
        finalPath = path;
        therePath = true;
        return;
    }

    for(int i = 0; i < 4; i++) {
        
        int dy = parent.first + movs[i][0];
        int dx = parent.second + movs[i][1];

        if(isValid(grid, n, m, {dy, dx})) {

            visited[dy][dx] = true;
            path.push_back({dy, dx});
            getPath(grid, n, m, path, target, {dy, dx});
            path.pop_back();
            visited[dy][dx] = false;
        }
    }
}
int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    therePath = false;
    int n, m;
    cin >> n >> m;

    visited = vector<vector<bool>>(n, vector<bool>(m, false));
    vector<string> grid(n);
    for(int i = 0; i < n; i++) {
        cin >> grid[i];
    }

    pii source, target;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(grid[i][j] == 'S') {
                source = {i, j};
            }
            else if(grid[i][j] == 'T') {
                target = {i, j};
            }
        }
    }

    vpii path;
    path.push_back(source);
    visited[source.first][source.second] = true;

    getPath(grid, n, m, path, target, source);
    if ( therePath ) {

        int direction = -1;
        int countChangeDirection = 0;

        for(int i = 0; i+1 < 2 and i+1 < finalPath.size(); i++) {
            direction = finalPath[i].first * finalPath[i + 1].second -
                    finalPath[i + 1].first * finalPath[i].second;
        }

        for(int i = 1; i + 1 < finalPath.size(); i++) {
            int currDirection = finalPath[i].first * finalPath[i + 1].second -
                    finalPath[i + 1].first * finalPath[i].second;
            if(currDirection != direction) countChangeDirection++;
            direction = currDirection;
        }

        if(countChangeDirection <= 2) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    } else {
        cout << "NO" << '\n';
    }
    
    return 0;
}