/* -*- coding: utf-8 -*- * * 3599.cc: No.3599 Queen Moving Query - yukicoder */ #include #include #include #include using namespace std; /* constant */ const int MAX_HW = 100000; const int MAX_GN = MAX_HW * 2; const int INF = 1 << 30; const int dxs[] = {0, -1, -1, -1, 0, 1, 1, 1}; const int dys[] = {1, 1, 0, -1, -1, -1, 0, 1}; /* typedef */ using pii = pair; /* global variables */ char s[MAX_HW + 4]; int ds[MAX_GN]; /* subroutines */ /* main */ int main() { int h, w, sx, sy; scanf("%d%d%d%d", &h, &w, &sx, &sy); sx--, sy--; for (int i = 0; i < h; i++) scanf("%s", s + i * w); int hw = h * w, gn = hw * 2; fill(ds, ds + gn, INF); int st = (sx * w + sy) << 1; ds[st] = 0; priority_queue q; q.push({0, st}); while (! q.empty()) { auto [ud, u] = q.top(); q.pop(); ud = -ud; if (ds[u] != ud) continue; int up = (u >> 1), uz = (u & 1); int ux = up / w, uy = up % w; int vz = (uz ^ 1), vd = ud + 1; for (int di = 0; di < 8; di++) { int dx = dxs[di], dy = dys[di]; int vx = ux + dx, vy = uy + dy, z = 1; while (vx >= 0 && vx < h && vy >= 0 && vy < w) { int vp = vx * w + vy; if (s[vp] == '#') break; int v = (vp << 1) | vz; if (ds[v] > vd) ds[v] = vd, q.push({-vd, v}); if (z > 1) { int v1 = v ^ 1; if (ds[v1] > vd) ds[v1] = vd, q.push({-vd, v1}); } vx += dx, vy += dy, z++; } } } int qn; scanf("%d", &qn); while (qn--) { int gx, gy, t; scanf("%d%d%d", &gx, &gy, &t); gx--, gy--; int gp = gx * w + gy; int g0 = (gp << 1), g1 = (g0 | 1); int tp = (t & 1); //printf(" gx,gy=%d,%d t=%d: d0=%d d1=%d\n", gx, gy, t, ds[g0], ds[g1]); if ((tp == 0 && ds[g0] <= t) || (tp == 1 && ds[g1] <= t)) puts("Yes"); else puts("No"); } return 0; }