結果

問題 No.3599 Queen Moving Query
コンテスト
ユーザー kidodesu
提出日時 2026-07-25 00:02:44
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 2,010 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 233 ms
コンパイル使用メモリ 95,964 KB
実行使用メモリ 279,956 KB
最終ジャッジ日時 2026-07-25 00:03:15
合計ジャッジ時間 25,403 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 23 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def main():
    h, w, sy, sx = list(map(int, input().split()))
    sy, sx = sy-1, sx-1
    inf = 1<<60
    S = [input() for _ in range(h)]
    D0 = [[[inf]*9 for _ in range(w)] for _ in range(h)]
    D1 = [[[inf]*9 for _ in range(w)] for _ in range(h)]
    B = [(sy, sx, 8)]
    D0[sy][sx][8] = 0
    dy = [1, 1, 1, 0, -1, -1, -1, 0]
    dx = [1, 0, -1, -1, -1, 0, 1, 1]
    c = 0
    mx = 0
    while A:= B:
        B = []
        if c % 2 == 0:
            D = D0
            D_ = D1
        else:
            D = D1
            D_ = D0
        while A:
            mx += 1
            y, x, d = A.pop()
            if D[y][x][d] < c: continue
            for nd in range(8):
                ny, nx = y, x
                for _ in range(2):
                    ny, nx = ny+dy[nd], nx+dx[nd]
                    if d == nd:
                        if 0 <= ny < h and 0 <= nx < w and S[ny][nx] == ".":
                            if c < D[ny][nx][nd]:
                                D[ny][nx][nd] = c
                                A.append((ny, nx, nd))
                        else:
                            break
                    else:
                        if 0 <= ny < h and 0 <= nx < w and S[ny][nx] == ".":
                            if c+1 < D_[ny][nx][nd]:
                                D_[ny][nx][nd] = c+1
                                B.append((ny, nx, nd))
                        else:
                            break
        c += 1
    if mx == 1:
        for _ in range(int(input())):
            gy, gx, t = list(map(lambda x: int(x)-1, input().split()))
            print("Yes" if (gy, gx) == (sy, sx) else "No")
    else:
        for _ in range(int(input())):
            gy, gx, t = list(map(lambda x: int(x)-1, input().split()))
            t += 1
            if t % 2:
                D = D1
            else:
                D = D0
            ma = min(D[gy][gx])
            if ma <= t:
                print("Yes")
            else:
                print("No")

main()
0