#1173270 (C++23) No.3599 Queen Moving Query

• 問題: No.3599 Queen Moving Query
• ユーザー: yaaya
• 提出日時: 2026-07-24 22:52:08
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: WA
• 実行時間: -
• コード長: 3,921 bytes
• コンパイル時間: 2,413 ms
• コンパイル使用メモリ: 352,588 KB
• 実行使用メモリ: 50,732 KB
• 最終ジャッジ日時: 2026-07-24 22:52:33
• 合計ジャッジ時間: 6,509 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 2
other	AC * 23 WA * 3

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a-1;i>=b;i--)
#define ll long long
#define ull unsigned ll
#define ld long double
#define bl __int128_t
#define fi first
#define se second
#define vel vector<ll>
#define vvel vector<vel>
#define pll pair<ll,ll>
#define vepll vector<pll>
#define vvepll vector<vepll>
#define ves vector<string>
#define vem vector<mint>
#define vvem vector<vem>
#define pmm pair<mint,mint>
#define vepmm vector<pmm>
#define cleout(i) cout<<fixed<<setprecision(i)
template<class T>using PQ=priority_queue<T,vector<T>,greater<T>>;
//               上  右 下 左
vector<int> di={-1, 0, 1, 0};
vector<int> dj={ 0, 1, 0,-1};

vector<int> dx={ 0, 1, 0,-1};
vector<int> dy={ 1, 0,-1, 0};


vector<int> ddx={ 1, 1, 1, 0, -1, -1, -1, 0 };
vector<int> ddy={ 1, 0, -1, -1, -1, 0, 1, 1 };

ll inf=1000000000000000000;//1e18
// LLONG_MAX

mt19937_64 rng((ull)chrono::steady_clock::now().time_since_epoch().count());

//[x^M]1/(1-x)^N=comb(N-1+M,M)

struct info{
    ll d;
    pll now;
    ll t;
    info(ll D=-1,pll NOW={-1,-1},ll T=inf){
        d=D;
        now=NOW;
        t=T;
    }
};

void _solve(){
    ll H,W,x,y;
    cin>>H>>W>>x>>y;
    x--;
    y--;
    vector<vvel> seen0(H,vvel(W,vel(8,inf))),seen1(H,vvel(W,vel(8,inf)));
    vvel a(H,vel(W,0));
    rep(i,0,H){
        string S;
        cin>>S;
        rep(j,0,W){
            if(S[j]=='#')a[i][j]=1;
        }
    }
    deque<info> qu;
    rep(i,0,8)seen0[x][y][i]=0;
    auto check=[&](pll now){
        if(0<=now.fi&&now.fi<H&&0<=now.se&&now.se<W){
            return (bool)(a[now.fi][now.se]==0);
        }
        return false;
    };
    rep(i,0,8){
        pll now={x+ddx[i],y+ddy[i]};
        if(check(now)){
            info p(i,now,1);
            qu.push_back(p);
            seen1[now.fi][now.se][i]=1;
        }
    }
    bool flg=0;
    if(qu.size()==0)flg=1;
    while(qu.size()){
        info now=qu.front();
        qu.pop_front();
        rep(i,0,8){
            pll nnow={now.now.fi+ddx[i],now.now.se+ddy[i]};
            if(check(nnow)){
                if((now.t+(now.d!=i))%2==0){
                    if(seen0[nnow.fi][nnow.se][i]>now.t+(now.d!=i)){
                        seen0[nnow.fi][nnow.se][i]=now.t+(now.d!=i);
                        if(now.d==i){
                            info p(i,nnow,now.t);
                            qu.push_front(p);
                        }else{
                            info p(i,nnow,now.t+1);
                            qu.push_back(p);
                        }
                    }
                }else{
                    if(seen1[nnow.fi][nnow.se][i]>now.t+(now.d!=i)){
                        seen1[nnow.fi][nnow.se][i]=now.t+(now.d!=i);
                        if(now.d==i){
                            info p(i,nnow,now.t);
                            qu.push_front(p);
                        }else{
                            info p(i,nnow,now.t+1);
                            qu.push_back(p);
                        }
                    }
                }
            }
        }
    }
    ll Q;
    cin>>Q;
    rep(i,0,Q){
        ll dx,dy,t;
        cin>>dx>>dy>>t;
        dx--;
        dy--;
        if(flg){
            return ;
            cout<<"No\n";
            continue;
        }
        if(t%2){
            ll ans=inf;
            rep(j,0,8){
                ans=min(ans,seen1[dx][dy][j]);
            }
            if(ans<=t)cout<<"Yes\n";
            else cout<<"No\n";
        }else{
            ll ans=inf;
            rep(j,0,8){
                ans=min(ans,seen0[dx][dy][j]);
            }
            if(ans<=t)cout<<"Yes\n";
            else cout<<"No\n";
        }
    }
}



int main(){
    cin.tie(nullptr);
 	ios_base::sync_with_stdio(false);
    
    ll _;
    bool multitest=0;
    if(multitest)cin>>_;
    else _=1;
    rep(__,0,_){
        _solve();
    }
}