/* -*- 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 << 4; 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 << 4; fill(ds, ds + gn, INF); priority_queue q; for (int di = 0; di < 8; di++) ds[((sx * w + sy) << 4) | (di << 1) | 0] = 0; for (int di = 0; di < 8; di++) { int vx = sx + dxs[di], vy = sy + dys[di]; if (vx >= 0 && vx < h && vy >= 0 && vy < w) { int vp = vy * w + vx; if (s[vp] == '.') { int v = (vp << 4) | (di << 1) | 1; ds[v] = 1, q.push({-1, v}); } } } while (! q.empty()) { auto [ud, u] = q.top(); q.pop(); ud = -ud; if (ds[u] != ud) continue; int up = (u >> 4), udi = ((u >> 1) & 7), uz = (u & 1); int ux = up / w, uy = up % w; int vz = (uz ^ 1); for (int vdi = 0; vdi < 8; vdi++) { int vx = ux + dxs[vdi], vy = uy + dys[vdi]; if (vx >= 0 && vx < h && vy >= 0 && vy < w) { int vp = vx * w + vy; if (s[vp] == '.') { int v = (vp << 4) | (vdi << 1) | vz; int vd = ud + (udi != vdi ? 1 : 0); if (ds[v] > vd) ds[v] = vd, q.push({-vd, v}); if (udi == vdi) { int v1 = v ^ 1; if (ds[v1] > vd) ds[v1] = vd, q.push({-vd, v1}); } } } } } 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 tp = (t & 1); int d0 = INF, d1 = INF; for (int di = 0; di < 8; di++) { int g0 = (gp << 4) | (di << 1), g1 = (g0 | 1); d0 = min(d0, ds[g0]); d1 = min(d1, ds[g1]); } if ((tp == 0 && d0 <= t) || (tp == 1 && d1 <= t)) puts("Yes"); else puts("No"); } return 0; }