結果
| 問題 | No.3599 Queen Moving Query |
| コンテスト | |
| ユーザー |
 titia
|
| 提出日時 | 2026-08-01 02:28:55 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,093 bytes |
| 記録 | |
| コンパイル時間 | 426 ms |
| コンパイル使用メモリ | 96,484 KB |
| 実行使用メモリ | 111,636 KB |
| 最終ジャッジ日時 | 2026-08-01 02:29:14 |
| 合計ジャッジ時間 | 10,764 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 20 WA * 6 |
ソースコード
import sys
input = sys.stdin.readline
from collections import deque
H,W,sx,sy=list(map(int,input().split()))
S=[input().strip() for i in range(H)]
DP0=[[1<<60]*W for i in range(H)]
DP1=[[1<<60]*W for i in range(H)]
sx-=1
sy-=1
DP0[sx][sy]=0
Q=deque()
Q.append((sx,sy,0))
while Q:
#print(Q)
x,y,kai=Q.popleft()
if kai%2==0:
for z in range(1,10**6):
if 0<=x+z<H and 0<=y<W and S[x+z][y]!="#":
if DP1[x+z][y]>kai+1:
DP1[x+z][y]=kai+1
Q.append((x+z,y,kai+1))
else:
break
else:
break
for z in range(1,10**6):
if 0<=x-z<H and 0<=y<W and S[x-z][y]!="#":
if DP1[x-z][y]>kai+1:
DP1[x-z][y]=kai+1
Q.append((x-z,y,kai+1))
else:
break
else:
break
for z in range(1,10**6):
if 0<=x<H and 0<=y+z<W and S[x][y+z]!="#":
if DP1[x][y+z]>kai+1:
DP1[x][y+z]=kai+1
Q.append((x,y+z,kai+1))
else:
break
else:
break
for z in range(1,10**6):
if 0<=x<H and 0<=y-z<W and S[x][y-z]!="#":
if DP1[x][y-z]>kai+1:
DP1[x][y-z]=kai+1
Q.append((x,y-z,kai+1))
else:
break
else:
break
for z in range(1,10**6):
if 0<=x+z<H and 0<=y+z<W and S[x+z][y+z]!="#":
if DP1[x+z][y+z]>kai+1:
DP1[x+z][y+z]=kai+1
Q.append((x+z,y+z,kai+1))
else:
break
else:
break
for z in range(1,10**6):
if 0<=x-z<H and 0<=y+z<W and S[x-z][y+z]!="#":
if DP1[x-z][y+z]>kai+1:
DP1[x-z][y+z]=kai+1
Q.append((x-z,y+z,kai+1))
else:
break
else:
break
for z in range(1,10**6):
if 0<=x+z<H and 0<=y-z<W and S[x+z][y-z]!="#":
if DP1[x+z][y-z]>kai+1:
DP1[x+z][y-z]=kai+1
Q.append((x+z,y-z,kai+1))
elif DP1[x+z][y-z]==kai+1:
pass
else:
break
else:
break
for z in range(1,10**6):
if 0<=x-z<H and 0<=y-z<W and S[x-z][y-z]!="#":
if DP1[x-z][y-z]>kai+1:
DP1[x-z][y-z]=kai+1
Q.append((x-z,y-z,kai+1))
else:
break
else:
break
else:
for z in range(1,10**6):
if 0<=x+z<H and 0<=y<W and S[x+z][y]!="#":
if DP0[x+z][y]>kai+1:
DP0[x+z][y]=kai+1
Q.append((x+z,y,kai+1))
else:
break
else:
break
for z in range(1,10**6):
if 0<=x-z<H and 0<=y<W and S[x-z][y]!="#":
if DP0[x-z][y]>kai+1:
DP0[x-z][y]=kai+1
Q.append((x-z,y,kai+1))
else:
break
else:
break
for z in range(1,10**6):
if 0<=x<H and 0<=y+z<W and S[x][y+z]!="#":
if DP0[x][y+z]>kai+1:
DP0[x][y+z]=kai+1
Q.append((x,y+z,kai+1))
else:
break
else:
break
for z in range(1,10**6):
if 0<=x<H and 0<=y-z<W and S[x][y-z]!="#":
if DP0[x][y-z]>kai+1:
DP0[x][y-z]=kai+1
Q.append((x,y-z,kai+1))
else:
break
else:
break
for z in range(1,10**6):
if 0<=x+z<H and 0<=y+z<W and S[x+z][y+z]!="#":
if DP0[x+z][y+z]>kai+1:
DP0[x+z][y+z]=kai+1
Q.append((x+z,y+z,kai+1))
elif DP0[x+z][y+z]==kai+1:
pass
else:
break
else:
break
for z in range(1,10**6):
if 0<=x-z<H and 0<=y+z<W and S[x-z][y+z]!="#":
if DP0[x-z][y+z]>kai+1:
DP0[x-z][y+z]=kai+1
Q.append((x-z,y+z,kai+1))
else:
break
else:
break
for z in range(1,10**6):
if 0<=x+z<H and 0<=y-z<W and S[x+z][y-z]!="#":
if DP0[x+z][y-z]>kai+1:
DP0[x+z][y-z]=kai+1
Q.append((x+z,y-z,kai+1))
else:
break
else:
break
for z in range(1,10**6):
if 0<=x-z<H and 0<=y-z<W and S[x-z][y-z]!="#":
if DP0[x-z][y-z]>kai+1:
DP0[x-z][y-z]=kai+1
Q.append((x-z,y-z,kai+1))
else:
break
else:
break
c=0
for i in range(H):
for j in range(W):
if DP0[i][j]!=1<<60:
c=max(c,DP0[i][j])
if DP1[i][j]!=1<<60:
c=max(c,DP1[i][j])
Q=int(input())
for tests in range(Q):
gx,gy,T=list(map(int,input().split()))
gx-=1
gy-=1
if c==0:
print("No")
continue
if T%2==0:
if DP0[gx][gy]==1<<60:
print("No")
else:
if DP0[gx][gy]<=T:
print("Yes")
else:
print("No")
else:
if DP1[gx][gy]==1<<60:
print("No")
else:
if DP1[gx][gy]<=T:
print("Yes")
else:
print("No")