Sol: B. Igor and his way to work (TLE)

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define loop(n) for(int i=0; i<n; i++)
#define rep(i, a, n) for(int i=a; i<n; i++)
#define file_read freopen("input.txt", "r", stdin); \
                  freopen("output.txt", "w", stdout);
#define tc int t; cin>>t; while(t--)
#define endl "\n"
#define usainbolt cin.tie(0) -> sync_with_stdio(0)

int mat[1000][1000];
int n, m;

/*
0 - up
1 - right
2 - down
3 - left
*/

int offset[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
int opp_dir[4] = {2, 3, 0, 1};

bool inbounds(int x, int y, int direction){
    int offset_x = offset[direction][0], offset_y = offset[direction][1];
    x += offset_x;
    y += offset_y;
    if(x<m && x>=0 && y<n && y>=0){
        if(mat[y][x]!='*')
            return true;
        else
            return false;
    }
    return false;
}

bool possible = false;

void solve_rec(int cur_dir, int x, int y, int turns){

    if(mat[y][x]=='T'){
        possible = true;
        return;
    }

    for(; inbounds(x, y, cur_dir);){
        x += offset[cur_dir][0];
        y += offset[cur_dir][1];
        for(int i=0; i<4 && turns <= 2; i++){
            if(i==cur_dir || i==opp_dir[cur_dir])
                continue;
            if(turns < 2 && inbounds(x, y, i))
                solve_rec(i, x+offset[i][0], y+offset[i][1],turns+1);
        }
        if(mat[y][x]=='T'){
            possible = true;
            return;
        }
    }

}
// ..S..****.T....****......
int main(void){
    usainbolt;
    //file_read
    cin>>n>>m;

    int h_x, h_y, b_x, b_y;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            char inp;
            cin>>inp;
            mat[i][j] = inp;
            if(mat[i][j]=='S')
            {
                h_x = j;
                h_y = i;
            }
        }
    }

    solve_rec(0, h_x, h_y, 0);
    solve_rec(1, h_x, h_y, 0);
    solve_rec(2, h_x, h_y, 0);
    solve_rec(3, h_x, h_y, 0);

    if(possible)
        cout << "YES";
    else
        cout << "NO";

}