use std::collections::VecDeque; use proconio::{ fastout, input, marker::{Chars, Usize1}, }; #[fastout] fn main() { input! { h: usize, w: usize, sx: Usize1, sy: Usize1, s: [Chars; h], q: usize, queries: [(Usize1, Usize1, usize); q], } let delta = [ (-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1), ]; let mut dist = vec![vec![[[!0usize; 2]; 8]; w]; h]; let mut que = VecDeque::new(); for dir in 0..8 { dist[sx][sy][dir][0] = 0; que.push_back((sx, sy, dir, 0)); } let mut can_move = false; while let Some((i, j, dir, parity)) = que.pop_front() { let now = dist[i][j][dir][parity]; for (ndir, &(di, dj)) in delta.iter().enumerate() { let ni = i.wrapping_add_signed(di); let nj = j.wrapping_add_signed(dj); if ni >= h || nj >= w || s[ni][nj] == '#' { continue; } if now != 0 && dir == ndir { let nparity = parity; if dist[ni][nj][ndir][nparity] == !0 { dist[ni][nj][ndir][nparity] = now; que.push_front((ni, nj, ndir, nparity)); can_move |= true; } } { let nparity = parity ^ 1; if dist[ni][nj][ndir][nparity] == !0 { dist[ni][nj][ndir][nparity] = now + 1; que.push_back((ni, nj, ndir, nparity)); can_move |= true; } } } } for &(gx, gy, t) in &queries { let parity = t % 2; let min = (0..8).map(|dir| dist[gx][gy][dir][parity]).min().unwrap(); let ans = can_move && min <= t; println!("{}", if ans { "Yes" } else { "No" }); } }