IPST58: Pacman and Ghost

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

const int N = 100;

pii dir[4] = {pii(0, 1), pii(0, -1), pii(1, 0), pii(-1, 0)};
pii dirP[5] = {pii(0, 0), pii(0, 1), pii(0, -1), pii(1, 0), pii(-1, 0)};
char board[N][N + 1];
int dist[N][N], row, col;
bool visited[N][N];

bool isInBoard(int r, int c){
    return r >= 0 && r < row && c >= 0 && c < col;
}

int main(){

    int Q;
    scanf("%d", &Q);
    while(Q--){
        int nGhost, tr, stR, stC;
        scanf("%d%d%d%d%d%d", &row, &col, &nGhost, &tr, &stR, &stC);
        priority_queue<tiii, vector<tiii>, greater<tiii>> pq;
        for(int i = 0; i < row; ++i){
            for(int j = 0; j < col; ++j){
                dist[i][j] = 1e9;
                visited[i][j] = false;
            }
        }
        for(int i = 1; i <= nGhost; ++i){
            int d, r, c;
            scanf("%d%d%d", &d, &r, &c);
            if(d < dist[r][c]){
                pq.emplace(d, r, c);
                dist[r][c] = d;
            }
        }
        for(int i = 0; i < row; ++i){
            for(int j = 0; j < col; ++j){
                scanf(" %c", &board[i][j]);
            }
        }
        while(!pq.empty()){
            int ur = get<1>(pq.top());
            int uc = get<2>(pq.top());
            pq.pop();
            if(visited[ur][uc]){
                continue;
            }
            visited[ur][uc] = true;
            for(int d = 0; d < 4; ++d){
                int vr = ur + dir[d].first;
                int vc = uc + dir[d].second;
                if(isInBoard(vr, vc) && board[vr][vc] != '#' && !visited[vr][vc] && dist[ur][uc] + 1 < dist[vr][vc]){
                    dist[vr][vc] = dist[ur][uc] + 1;
                    pq.emplace(dist[vr][vc], vr, vc);
                }
            }
        }
        queue<pii> que;
        if(dist[stR][stC] == 0){
            cout << "NO\n";
            continue;
        }
        que.emplace(stR, stC);
        int t, cnt = 1;
        for(t = 0; t < tr; ++t){
            for(int i = 0; i < row; ++i){
                for(int j = 0; j < col; ++j){
                    visited[i][j] = false;
                }
            }
            int newCnt = 0;
            for(int i = 1; i <= cnt && !que.empty(); ++i){
                int ur = que.front().first;
                int uc = que.front().second;
                que.pop();
                for(int d = 0; d < 5; ++d){
                    int vr = ur + dirP[d].first;
                    int vc = uc + dirP[d].second;
                    if(isInBoard(vr, vc) && board[vr][vc] != '#' && !visited[vr][vc] && t + 1 < dist[vr][vc]){
                        visited[vr][vc] = true;
                        ++newCnt;
                        que.emplace(vr, vc);
                    }
                }
            }
            cnt = newCnt;
            if(cnt == 0){
                break;
            }
        }
        if(t == tr){
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }

    return 0;
}