Day 3. D. Vikings and Treasure

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define pb push_back
#define int long long
#define uint __int128
#define mp make_pair
#define left left_compile
#define right right_compile

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

const int INF = (int)1e18;
const int md = (int)1e9 + 7;
const int MAXN = (int)1e6 + 111;
const int N = (int)700 + 11;
const int debug = 0;
const long double eps = 1e-7;

typedef tree<
int,
null_type,
less_equal<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

int bpow(int a,int b){
    if(b == 0)
        return 1ll;
    if(b % 2 == 0){
        int t = bpow(a,b/2);
        return (t * t) % md;
    }
    return (a * bpow(a,b-1)) % md;
}

int inv(int a){ /// return 1/a by PRIME modulo md
    return bpow(a,md-2);
}

void myerase(ordered_set& st, int t){
    int r = st.order_of_key(t);
    ordered_set::iterator it = st.find_by_order(r);
    st.erase(it);
    return;
}

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

void init(){
    return;
}

const int DX[] = {0,1,0,-1};
const int DY[] = {1,0,-1,0};

bool g[N][N];
int d[3][N][N];

void solve_case(){
    int n,m;
    cin >> n >> m;

    string s;
    int Vx,Vy;
    int Sx,Sy;
    int Fx,Fy;
    for(int i = 0; i <= n + 1; i++){
        for(int j = 0; j <= m + 1; j++){
            g[i][j] = true;
            d[0][i][j] = d[1][i][j] = d[2][i][j] = INF;
        }
    }
    for(int i = 1; i <= n; i++){
        cin >> s;
        for(int j = 1; j <= m; j++){
            if(s[j-1] == 'I')
                g[i][j] = true;
            else
                g[i][j] = false;
            if(s[j-1] == 'V')
                Vx = i, Vy = j;
            if(s[j-1] == 'Y')
                Sx = i, Sy = j;
            if(s[j-1] == 'T')
                Fx = i, Fy = j;
        }
    }

    d[0][Vx][Vy] = 0;
    deque<pair<int,int>> q;
    q.push_front(mp(Vx,Vy));
    while(!q.empty()){
        int x = q.front().first, y = q.front().second;
        q.pop_front();
        for(int i = 0; i < 4; i++){
            int xn = x + DX[i], yn = y + DY[i];
            if(xn > 0 && xn <= n && yn > 0 && yn <= m && !g[xn][yn] && d[0][xn][yn] > d[0][x][y] + 1){
                q.push_back(mp(xn,yn));
                d[0][xn][yn] = d[0][x][y] + 1;
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            for(int t = j; t > 0; t--){
                if(g[i][t])
                    break;
                d[1][i][t] = min(d[1][i][t],d[0][i][j]);
            }
            for(int t = j; t <= m; t++){
                if(g[i][t])
                    break;
                d[1][i][t] = min(d[1][i][t],d[0][i][j]);
            }
            for(int t = i; t > 0; t--){
                if(g[t][j])
                    break;
                d[1][t][j] = min(d[1][t][j],d[0][i][j]);
            }
            for(int t = i; t <= n; t++){
                if(g[t][j])
                    break;
                d[1][t][j] = min(d[1][t][j],d[0][i][j]);
            }
        }
    }

    d[2][Sx][Sy] = 0;
    q.push_back(mp(Sx,Sy));
    while(!q.empty()){
        int x = q.front().first, y = q.front().second;
        q.pop_front();
        for(int i = 0; i < 4; i++){
            int xn = x + DX[i], yn = y + DY[i];
            if(xn > 0 && xn <= n && yn > 0 && yn <= m && !g[xn][yn] && d[2][xn][yn] > d[2][x][y] + 1
            && d[2][x][y] + 1 < d[1][xn][yn]){
                q.push_back(mp(xn,yn));
                d[2][xn][yn] = d[2][x][y] + 1;
            }
        }
    }

    if(d[2][Fx][Fy] == INF)
        cout << "NO";
    else
        cout << "YES";

    return;
}

signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);

    init();

    int tests = 1;
//    cin >> tests;

    for(int _ = 1; _ <= tests; _++){
        solve_case();
    }

    return 0;
}

/*
.Y.....
..I....
..IIIII
..Y....
...T...

*/