結果

問題 No.3599 Queen Moving Query
コンテスト
ユーザー kidodesu
提出日時 2026-07-24 22:11:46
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 2,691 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 254 ms
コンパイル使用メモリ 96,104 KB
実行使用メモリ 202,492 KB
最終ジャッジ日時 2026-07-24 22:12:01
合計ジャッジ時間 14,249 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21 WA * 5
権限があれば一括ダウンロードができます

ソースコード

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)]
    D = [[[inf]*8 for _ in range(w)] for _ in range(h)]
    D[sy][sx] = [1] * 8
    B = [(sy, sx, i) for i in range(8)]
    dy = [1, 1, 1, 0, -1, -1, -1, 0]
    dx = [1, 0, -1, -1, -1, 0, 1, 1]
    c = 1
    while A:= B:
        B = []
        while A:
            y, x, d = A.pop()
            if D[y][x][d] < c: continue
            for nd in range(8):
                ny, nx = y+dy[nd], x+dx[nd]
                if d == nd:
                    if 0 <= ny < h and 0 <= nx < w and c < D[ny][nx][nd] and S[ny][nx] == ".":
                        D[ny][nx][nd] = c
                        A.append((ny, nx, nd))
                else:
                    if 0 <= ny < h and 0 <= nx < w and c+1 < D[ny][nx][nd] and S[ny][nx] == ".":
                        D[ny][nx][nd] = c+1
                        B.append((ny, nx, nd))
        c += 1
    X = [[-1 if min(D[y][x]) != inf else -2 for x in range(w)] for y in range(h)]
    S = [(sy, sx)]
    X[sy][sx] = 0
    f = 1
    c = 0
    while S and f:
        c += 1
        y, x = S.pop()
        for d in range(8):
            ny, nx = y, x
            f = 0
            for _ in range(2):
                f ^= 1
                ny, nx = ny+dy[d], nx+dx[d]
                if not (0 <= ny < h and 0 <= nx < w):
                    break
                if X[ny][nx] == -2:
                    break
                if X[ny][nx] == -1:
                    X[ny][nx] = X[y][x]^1
                    S.append((ny, nx))
                else:
                    if X[ny][nx]^X[y][x]^1:
                        f = 0
                        break
            else:
                f = 0
                break
    if c == 1 and f:
        for _ in range(int(input())):
            gy, gx, t = list(map(lambda x: int(x)-1, input().split()))
            t += 1
            if (gy, gx) == (sy, sx):
                print("Yes")
            else:
                print("No")
    elif not f:
        for _ in range(int(input())):
            gy, gx, t = list(map(lambda x: int(x)-1, input().split()))
            t += 1
            ma = min(D[gy][gx])
            if ma <= t:
                print("Yes")
            else:
                print("No")
    else:
        for _ in range(int(input())):
            gy, gx, t = list(map(lambda x: int(x)-1, input().split()))
            t += 1
            if (sy, sx) == (gy, gx):
                print("Yes" if not t % 2 else "No")
            elif min(D[gy][gx]) != inf:
                print("Yes" if t % 2 else "No")
            else:
                print("No")

main()
0