#include #include #include #include #include using namespace std; int main(){ int H, W, sx, sy; cin >> H >> W >> sx >> sy; sx--; sy--; vector S(H); for (int i = 0; i < H; i++){ cin >> S[i]; } int Q; cin >> Q; vector gx(Q); vector gy(Q); vector T(Q); for (int i = 0; i < Q; i++){ cin >> gx[i] >> gy[i] >> T[i]; gx[i]--; gy[i]--; } vector dx = {1, 1, 0, -1, -1, -1, 0, 1}; vector dy = {0, 1, 1, 1, 0, -1, -1, -1}; bool movable = false; for (int i = 0; i < 8; i++){ if (sx + dx[i] >= 0 && sx + dx[i] < H && sy + dy[i] >= 0 && sy + dy[i] < W){ if (S[sx + dx[i]][sy + dy[i]] == '.'){ movable = true; } } } if (!movable){ for (int i = 0; i < Q; i++){ cout << "No" << endl; } return 0; } const int INF = 1000000007; vector>>> dist(H, vector>>(W, vector>(9, vector(2, INF)))); vector>>> isvisited(H, vector>>(W, vector>(9, vector(2, false)))); deque> dq; dq.push_front(make_tuple(sx, sy, 8, 0)); dist[sx][sy][8][0] = 0; while (dq.size()){ auto tp = dq.front(); dq.pop_front(); int px = get<0>(tp); int py = get<1>(tp); int dir = get<2>(tp); int id = get<3>(tp); if (isvisited[px][py][dir][id]){ continue; } isvisited[px][py][dir][id] = true; for (int i = 0; i < 8; i++){ int nx = px + dx[i]; int ny = py + dy[i]; if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue; if (S[nx][ny] == '#') continue; if (i == dir){ dq.push_front(make_tuple(nx, ny, i, id)); dist[nx][ny][i][id] = min(dist[nx][ny][i][id], dist[px][py][dir][id]); } dq.push_back(make_tuple(nx, ny, i, (id ^ 1))); dist[nx][ny][i][id ^ 1] = min(dist[nx][ny][i][id ^ 1], dist[px][py][dir][id] + 1); } } for (int i = 0; i < Q; i++){ int min_d = INF; for (int j = 0; j < 8; j++){ min_d = min(min_d, dist[gx[i]][gy[i]][j][T[i] % 2]); } if (min_d <= T[i]) cout << "Yes" << endl; else cout << "No" << endl; } }