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

• 問題: No.3599 Queen Moving Query
• ユーザー: nosu kuro
• 提出日時: 2026-07-24 22:46:47
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: TLE
• 実行時間: -
• コード長: 10,316 bytes
• コンパイル時間: 2,334 ms
• コンパイル使用メモリ: 350,432 KB
• 実行使用メモリ: 6,784 KB
• 最終ジャッジ日時: 2026-07-24 22:47:03
• 合計ジャッジ時間: 15,174 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_1

ファイルパターン	結果
sample	AC * 2
other	AC * 4 TLE * 1 -- * 21

ソースコード

#ifndef INCLUDED_MAIN
#define INCLUDED_MAIN

#include __FILE__



int main(void){
    int h, w; cin >> h >> w;
    pair<int,int> st;
    cin >> st.first >> st.second;
    st.first--; st.second--;
    vector<string> m(h);
    int i;
    rep(i,h){
        cin >> m[i];
    }

    vector<vector<int>> sc(h,vector<int>(w,-1)), sd(h,vector<int>(w,-1));
    

    queue<pair<bool,pair<int,int>>> 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<int,int> 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 <bits/stdc++.h>
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<int> dist(a,b);
    return dist(gen);
}

namespace nskr{

    //nyaan氏の実装をかなり参考にした
    template <int id = 0>
    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<id>(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<typename mint>
    struct combination{
        vector<mint> 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