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

• 問題: No.3599 Queen Moving Query
• ユーザー: askr58
• 提出日時: 2026-07-24 23:14:38
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 174 ms / 5,000 ms
• コード長: 1,523 bytes
• コンパイル時間: 1,410 ms
• コンパイル使用メモリ: 198,532 KB
• 実行使用メモリ: 23,552 KB
• 最終ジャッジ日時: 2026-07-24 23:14:53
• 合計ジャッジ時間: 6,400 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 2
other	AC * 26

ソースコード

#include <iostream>
#include <deque>
#include <string>
#include <ranges>
#include <algorithm>
#include <vector>
using namespace std;
using ll=long long;
int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int h,w;
	cin>>h>>w;
	int sx,sy;
	cin>>sx>>sy;
	sx--;sy--;
	vector<string> s(h);
	for(int i=0;i<h;i++)cin>>s[i];
	vector<int> dx={1,0,-1,0,1,1,-1,-1},dy={0,1,0,-1,1,-1,1,-1};
	vector dist(17,vector(h,vector<int>(w,2e9)));
	dist[0][sx][sy]=0;
	deque<array<int,4>> deq;
	deq.push_back({0,0,sx,sy});
	while(!deq.empty()){
		auto[d,c,x,y]=deq.front();
		deq.pop_front();
		if(d>dist[c][x][y])continue;
		//if(c==0)cout<<x<<" "<<y<<" "<<d<<endl;
		//else cout<<x<<" "<<y<<" "<<d<<" "<<dx[(c-1)%8]<<" "<<dy[(c-1)%8]<<endl;
		for(int r=0;r<8;r++){
			int nx=x+dx[r],ny=y+dy[r];
			if(nx<0||nx>=h||ny<0||ny>=w||s[nx][ny]=='#')continue;
			if(!(c==0||(c-1)%8!=r)){
				int w=0;
				int nc=1+r+8*((d+w)%2);
				if(dist[nc][nx][ny]<=d+w)continue;
				dist[nc][nx][ny]=d+w;
				if(w==0)deq.push_front({d,nc,nx,ny});
				else deq.push_back({d+1,nc,nx,ny});
			}
			{
				int w=1;
				int nc=1+r+8*((d+w)%2);
				if(dist[nc][nx][ny]<=d+w)continue;
				dist[nc][nx][ny]=d+w;
				if(w==0)deq.push_front({d,nc,nx,ny});
				else deq.push_back({d+1,nc,nx,ny});
			}
		}
	}

	int q;
	cin>>q;
	while(q--){
		int gx,gy,t;
		cin>>gx>>gy>>t;
		gx--;gy--;
		bool ok=false;
		for(int i=1;i<=16;i++){
			if(dist[i][gx][gy]<=t&&(t-dist[i][gx][gy])%2==0)ok=true;
		}
		if(ok)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
}