結果
| 問題 | No.3599 Queen Moving Query |
| コンテスト | |
| ユーザー |
 t0yama
|
| 提出日時 | 2026-07-24 23:11:19 |
| 言語 | C++23(gcc16) (gcc 16.1.0 + boost 1.90.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,168 bytes |
| 記録 | |
| コンパイル時間 | 3,437 ms |
| コンパイル使用メモリ | 378,560 KB |
| 実行使用メモリ | 33,968 KB |
| 最終ジャッジ日時 | 2026-07-24 23:11:29 |
| 合計ジャッジ時間 | 8,971 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 18 WA * 8 |
ソースコード
#include <bits/stdc++.h>
#define ull unsigned ll
#define ll long long
#define ld long double
#define INFL (ll)3e18
#define INF (int)2e9
#define MOD (ll)998244353
#define MODO (ll)(1e9+7)
using namespace std;
template<typename T>istream&operator>>(istream&is,vector<T>&v);
template<typename... Ts>istream&operator>>(istream&is,tuple<Ts...>& t);
template<typename T1,typename T2>istream&operator>>(istream&is,pair<T1,T2>&p){is>>p.first>>p.second;return is;}
template<typename T>istream&operator>>(istream&is,vector<T>&v){for(T&in:v)is>>in;return is;}
template<typename... Ts>istream& operator>>(istream& is, tuple<Ts...>& t) {apply([&](auto&... args) {((is >> args), ...);},t);return is;}
int main(void){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int h,w;
cin >> h >> w;
pair<int,int> s;
cin >> s;
vector<string> g(h);
cin >> g;
vector<ll> dst1(h*w,INFL),dst2(h*w,INFL);
vector<vector<pair<int,int>>> to(h*w);
vector<pair<int,int>> rle;
for(int i = 0;i < h;i++){
int st = 0;
for(int j = 0;j < w;j++){
if(g[i][j] == '#'){
if(st < j-1){
//cout << i << "," << st << " " << i << "," << j << endl;
dst1.push_back(INFL);
dst2.push_back(INFL);
to.push_back(vector<pair<int,int>>());
int be = to.size()-1;
for(;st < j;st++){
to[be].emplace_back(i*w+st,0);
to[i*w+st].emplace_back(be,1);
}
}
st = j+1;
}
}
if(st < w-1){
//cout << i << "," << st << " " << i << "," << w << endl;
dst1.push_back(INFL);
dst2.push_back(INFL);
to.push_back(vector<pair<int,int>>());
int be = to.size()-1;
for(;st < w;st++){
to[be].emplace_back(i*w+st,0);
to[i*w+st].emplace_back(be,1);
}
}
}
for(int j = 0;j < w;j++){
int st = 0;
for(int i = 0;i < h;i++){
if(g[i][j] == '#'){
if(st < i-1){
//cout << st << "," << j << " " << i << "," << j << endl;
dst1.push_back(INFL);
dst2.push_back(INFL);
to.push_back(vector<pair<int,int>>());
int be = to.size()-1;
for(;st < i;st++){
to[be].emplace_back(st*w+j,0);
to[st*w+j].emplace_back(be,1);
}
}
st = i+1;
}
}
if(st < h-1){
//cout << st << "," << j << " " << h << "," << j << endl;
dst1.push_back(INFL);
dst2.push_back(INFL);
to.push_back(vector<pair<int,int>>());
int be = to.size()-1;
for(;st < h;st++){
to[be].emplace_back(st*w+j,0);
to[st*w+j].emplace_back(be,1);
}
}
}
for(int i = 0;i < h+w;i++){
int st = 0;
for(int j = 0;j < h;j++){
int x = j,y = i-j;
if(y >= w){
st = j+1;
continue;
}
else if(y < 0) break;
if(g[x][y] == '#'){
if(st < x-1){
//cout << st << "," << i-st << " " << x << "," << y << endl;
dst1.push_back(INFL);
dst2.push_back(INFL);
to.push_back(vector<pair<int,int>>());
int be = to.size()-1;
for(;st < x;st++){
to[be].emplace_back(st*w+i-st,0);
to[st*w+i-st].emplace_back(be,1);
}
}
st = j+1;
}
}
if(st < h-1 && i-st >= 0 && i-st < w){
//cout << st << "," << i-st << " " << h << "," << i-h << endl;
dst1.push_back(INFL);
dst2.push_back(INFL);
to.push_back(vector<pair<int,int>>());
int be = to.size()-1;
for(;st < h && i-st < w && i-st >= 0;st++){
to[be].emplace_back(st*w+i-st,0);
to[st*w+i-st].emplace_back(be,1);
}
}
}
for(int i = 0;i < h+w;i++){
int st = 0;
for(int j = 0;j < h;j++){
int x = j,y = x+w-i;
if(y < 0){
st = j+1;
continue;
}
else if(y >= w) break;
if(g[x][y] == '#'){
if(st < x-1){
//cout << st << "," << st+w-i << " " << x << "," << y << endl;
dst1.push_back(INFL);
dst2.push_back(INFL);
to.push_back(vector<pair<int,int>>());
int be = to.size()-1;
for(;st < x;st++){
to[be].emplace_back(st*w+st+w-i,0);
to[st*w+st+w-i].emplace_back(be,1);
}
}
st = j+1;
}
}
if(st < h-1 && st+w-i >= 0 && st+w-i < w){
//cout << st << "," << st+w-i << " ";
dst1.push_back(INFL);
dst2.push_back(INFL);
to.push_back(vector<pair<int,int>>());
int be = to.size()-1;
for(;st < h && st+w-i >= 0 && st+w-i < w;st++){
to[be].emplace_back(st*w+st+w-i,0);
to[st*w+st+w-i].emplace_back(be,1);
}
//cout << st << "," << st+w-i << endl;
}
}
int dx[] = {1,1,1,0,0,-1,-1,-1},dy[] = {1,0,-1,1,-1,1,0,-1};
for(int i = 0;i < h;i++){
for(int j = 0;j < w;j++){
if(g[i][j] == '#') continue;
for(int k = 0;k < 8;k++){
int tx = i+dx[k],ty = j+dy[k];
if(tx < 0 || tx >= h || ty < 0 || ty >= w) continue;
if(g[tx][ty] == '#') continue;
to[i*w+j].emplace_back(tx*w+ty,1);
}
}
}
s.first--,s.second--;
deque<int> d;
ll S = s.first*w+s.second;
d.push_back(S);
dst1[S] = 0;
while(!d.empty()){
auto t = d.front();
d.pop_front();
for(auto& [i,j]:to[t]){
if(j == 0){
bool f = false;
if(dst1[i] > dst1[t]){
dst1[i] = dst1[t];
f = true;
}
if(dst2[i] > dst2[t]){
dst2[i] = dst2[t];
f = true;
}
if(f) d.push_front(i);
}
else{
bool f = false;
if(dst1[i] > dst2[t]+1){
dst1[i] = dst2[t]+1;
f = true;
}
if(dst2[i] > dst1[t]+1){
dst2[i] = dst1[t]+1;
f = true;
}
if(f) d.push_back(i);
}
}
}
int q;
cin >> q;
pair<int,int> go;
int t;
for(int i = 0;i < q;i++){
cin >> go >> t;
go.first--,go.second--;
ll G = go.first*w+go.second;
if(t%2){
if(dst2[G] <= t) cout << "Yes" << endl;
else cout << "No" << endl;
}
else{
if(dst1[G] <= t) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
/*
for(int i = 0;i < h;i++){
for(int j = 0;j < w;j++){
if(dst1[i*w+j] == INFL) cout << -1 << ",";
else cout << dst1[i*w+j] << ",";
if(dst2[i*w+j] == INFL) cout << -1 << " ";
else cout << dst2[i*w+j] << " ";
}
cout << endl;
}
for(int i = h*w;i < to.size();i++){
if(dst1[i] == INFL) cout << -1 << ",";
else cout << dst1[i] << ",";
if(dst2[i] == INFL) cout << -1 << " ";
else cout << dst2[i] << " ";
}
cout << endl;
//*/
}