ABC348D TLE

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifndef __DEBUG__
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vi = vector<int>;

int main(int argc, char **argv)
{
    ll h, w, n;
    cin >> h >> w;
    vector<string> mz(h);
    for (auto &s : mz)
        cin >> s;
    cin >> n;
    using a2l = array<ll, 2>;
    using a3l = array<ll, 3>;
    map<a2l, ll> eng, dist;
    for (ll i = 0, x, y, e; i < n; ++i)
        cin >> x >> y >> e, eng[{x - 1, y - 1}] = e;

    ll ds[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    bool reach = false;
    queue<a3l> q;
    ll s, t;
    for (ll i = 0; i < h; ++i)
        for (ll j = 0; j < w; ++j)
            if (mz[i][j] == 'S')
                s = i, t = j;
    q.push({0, s, t});
    while (!q.empty() && !reach) {
        auto [e, x, y] = q.front();
        q.pop();
        if (mz[x][y] == 'T')
            reach = true;
        if (eng.count({x, y}))
            e = max(e, eng[{x, y}]);
        auto &d = dist[{x, y}];
        d = max(d, e);
        if (e == 0)
            continue;
        for (ll i = 0; i < 4; ++i) {
            ll nx = x + ds[i][0], ny = y + ds[i][1];
            if (nx >= 0 && nx < h && ny >= 0 && ny < w && mz[nx][ny] != '#') {
                ll ne = eng.count({nx, ny}) ? max(eng[{nx, ny}], e - 1) : e - 1;
                if (dist.count({nx, ny}) == 0 || dist[{nx, ny}] < ne)
                    dist[{nx, ny}] = ne, q.push({ne, nx, ny});
            }
        }
    }
    cout << (reach ? "Yes\n" : "No\n");
    return 0;
};