#ifndef INCLUDED_MAIN #define INCLUDED_MAIN #include __FILE__ int main(void){ int h, w; cin >> h >> w; pair st; cin >> st.first >> st.second; st.first--; st.second--; vector m(h); int i; rep(i,h){ cin >> m[i]; } vector> sc(h,vector(w,-1)), sd(h,vector(w,-1)); queue>> q; q.push({false,st}); sc[st.first][st.second] = 0; while(!q.empty()){ auto [b,x] = q.front(); q.pop(); { auto nx = x; nx.first++; while(0<=nx.first && nx.first < h && nx.second>=0 && nx.second < w && m[nx.first][nx.second] != '#'){ if(!b){ if(sd[nx.first][nx.second] == -1){ sd[nx.first][nx.second] = sc[x.first][x.second]+1; q.push({true, nx}); } }else{ if(sc[nx.first][nx.second] == -1){ sc[nx.first][nx.second] = sd[x.first][x.second]+1; q.push({false, nx}); } } nx.first++; } nx = x; nx.second++; while(0<=nx.first && nx.first < h && nx.second>=0 && nx.second < w && m[nx.first][nx.second] != '#'){ if(!b){ if(sd[nx.first][nx.second] == -1){ sd[nx.first][nx.second] = sc[x.first][x.second]+1; q.push({true, nx}); } }else{ if(sc[nx.first][nx.second] == -1){ sc[nx.first][nx.second] = sd[x.first][x.second]+1; q.push({false, nx}); } } nx.second++; }nx = x; nx.first--; while(0<=nx.first && nx.first < h && nx.second>=0 && nx.second < w && m[nx.first][nx.second] != '#'){ if(!b){ if(sd[nx.first][nx.second] == -1){ sd[nx.first][nx.second] = sc[x.first][x.second]+1; q.push({true, nx}); } }else{ if(sc[nx.first][nx.second] == -1){ sc[nx.first][nx.second] = sd[x.first][x.second]+1; q.push({false, nx}); } } nx.first--; } nx = x; nx.second--; while(0<=nx.first && nx.first < h && nx.second>=0 && nx.second < w && m[nx.first][nx.second] != '#'){ if(!b){ if(sd[nx.first][nx.second] == -1){ sd[nx.first][nx.second] = sc[x.first][x.second]+1; q.push({true, nx}); }else{ break; } }else{ if(sc[nx.first][nx.second] == -1){ sc[nx.first][nx.second] = sd[x.first][x.second]+1; q.push({false, nx}); }else{ break; } } nx.second--; } nx = x; nx.first++;nx.second++; while(0<=nx.first && nx.first < h && nx.second>=0 && nx.second < w && m[nx.first][nx.second] != '#'){ if(!b){ if(sd[nx.first][nx.second] == -1){ sd[nx.first][nx.second] = sc[x.first][x.second]+1; q.push({true, nx}); }else{ break; } }else{ if(sc[nx.first][nx.second] == -1){ sc[nx.first][nx.second] = sd[x.first][x.second]+1; q.push({false, nx}); }else{ break; } } nx.first++;nx.second++; } nx = x; nx.second++;nx.first--; while(0<=nx.first && nx.first < h && nx.second>=0 && nx.second < w && m[nx.first][nx.second] != '#'){ if(!b){ if(sd[nx.first][nx.second] == -1){ sd[nx.first][nx.second] = sc[x.first][x.second]+1; q.push({true, nx}); }else{ break; } }else{ if(sc[nx.first][nx.second] == -1){ sc[nx.first][nx.second] = sd[x.first][x.second]+1; q.push({false, nx}); }else{ break; } } nx.second++;nx.first--; }nx = x; nx.first--;nx.second--; while(0<=nx.first && nx.first < h && nx.second>=0 && nx.second < w && m[nx.first][nx.second] != '#'){ if(!b){ if(sd[nx.first][nx.second] == -1){ sd[nx.first][nx.second] = sc[x.first][x.second]+1; q.push({true, nx}); }else{ break; } }else{ if(sc[nx.first][nx.second] == -1){ sc[nx.first][nx.second] = sd[x.first][x.second]+1; q.push({false, nx}); }else{ break; } } nx.first--;nx.second--; } nx = x; nx.second--;nx.first++; while(0<=nx.first && nx.first < h && nx.second>=0 && nx.second < w && m[nx.first][nx.second] != '#'){ if(!b){ if(sd[nx.first][nx.second] == -1){ sd[nx.first][nx.second] = sc[x.first][x.second]+1; q.push({true, nx}); }else{ break; } }else{ if(sc[nx.first][nx.second] == -1){ sc[nx.first][nx.second] = sd[x.first][x.second]+1; q.push({false, nx}); }else{ break; } } nx.second--;nx.first++; } } } int Q; cin >> Q; for(;Q--;){ pair tg; cin >> tg.first >> tg.second; ll t; cin >> t; if(t&1){ if(sd[tg.first-1][tg.second-1] <= t && sd[tg.first-1][tg.second-1] != -1){ cout << "Yes\n"; }else cout << "No\n"; }else{ if(sc[tg.first-1][tg.second-1] <= t && sc[tg.first-1][tg.second-1] != -1){ cout << "Yes\n"; }else cout << "No\n"; } } } #else #include using namespace std; using ll = long long; using ld = long double; #define rep(i,n) for(i=0;i<(n);i++) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() int randint(int a, int b){ static mt19937 gen(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution dist(a,b); return dist(gen); } namespace nskr{ //nyaan氏の実装をかなり参考にした template struct modint{ int v; static int& MOD(){ static int mod = 998244353; return mod; } static int get_mod() { return MOD(); } static void set_mod(int m) { MOD() = m; } modint() :v(0){} modint(long long x) : v( (x>=0 ? x%MOD() : (x%MOD() + MOD()))){} long long val() const {return v;} modint& operator+=(const modint& x){if((v+=x.v) >= MOD()) v-=MOD(); return *this; } modint& operator-=(const modint& x){if((v-=x.v) < 0 ) v+=MOD(); return *this; } modint& operator*=(const modint& x){v = (int)(1ll * v * x.v % MOD()); return *this;} modint& operator/=(const modint& x){v = (int)(1ll * v * x.inv().val() % MOD()); return *this;} modint operator-() const {return modint(-v);} modint operator+() const {return *this;} modint operator+(const modint& x) const {return modint(*this)+=x;} modint operator-(const modint& x) const {return modint(*this)-=x;} modint operator*(const modint& x) const {return modint(*this)*=x;} modint operator/(const modint& x) const {return modint(*this)/=x;} bool operator== (const modint& x) const {return v==x.v;} bool operator!= (const modint& x) const {return v!=x.v;} friend ostream &operator<<(ostream &os, const modint &p) { return os << p.v; } friend istream &operator>>(istream &is, modint &a) { int t; is >> t; a = modint(t); return (is); } modint pow(unsigned long long n) const { modint ret(1), mul(v); while(n){ if(n&1) ret *= mul; mul *= mul; n >>=1; } return ret; } modint inv() const{ //参考: https://qiita.com/sesame0224/items/f2ac77c367f588c0d29d int a = v, b = MOD(), u = 1, w = 0; while(b){ int t = a/b; swap(a -= t*b, b); swap(u -= t*w, w); } u%=MOD(); return(u<0?u+MOD():u); } }; template struct combination{ vector fac; combination():fac({mint(1)}){} void preculc(int n){ fac.reserve(n); while(fac.size() <= n){ fac.push_back( (*fac.rbegin()) * mint(fac.size()) ); } return; } mint comb(int n, int r){ if(r>n || r<0 || n<0) return 0; if(n-r < r) r = n-r; if(fac.size() > n) return fac[n] * fac[r].inv() * fac[n-r].inv(); else{ mint ret = fac[r].inv(); for(;r--;) ret *= (n-r+1); return ret; } } }; } #endif