結果

問題 No.3599 Queen Moving Query
コンテスト
ユーザー LyricalMaestro
提出日時 2026-07-25 15:29:44
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 560 ms / 5,000 ms
+ 578µs
コード長 2,709 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 230 ms
コンパイル使用メモリ 95,976 KB
実行使用メモリ 142,552 KB
最終ジャッジ日時 2026-07-25 15:30:00
合計ジャッジ時間 12,214 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# https://yukicoder.me/problems/no/3598

from collections import deque

MAX_INT = 10 ** 18

DIRECTIONS = [
    (1, 0),
    (0, 1),
    (-1, 0),
    (0, -1),
    (1, 1),
    (-1, -1),
    (1, -1),
    (-1, 1)
]

def main():
    H, W, sx, sy = map(int, input().split())
    S = []
    for _ in range(H):
        S.append(input())
    Q = int(input())
    queries = []
    for _ in range(Q):
        gx, gy, T = map(int, input().split())
        queries.append((gx - 1, gy - 1, T))

    sx -= 1
    sy -= 1
    # BFS
    dists = [[[MAX_INT for _ in range(1 + 8 + 1 + 8)] for _ in range(W)] for _ in range(H)]
    queue = deque()
    dists[sx][sy][0] = 0
    queue.append((sx, sy, 0))
    while len(queue) > 0:
        x, y, state = queue.popleft()

        if state % 9 == 0:
            for new_direction in range(1, 9):
                dx, dy = DIRECTIONS[new_direction - 1]
                new_x = dx + x
                new_y = dy + y
                new_state = new_direction + state
                if 0 <= new_x < H and 0 <= new_y < W:
                    if S[new_x][new_y] == ".":
                        if dists[new_x][new_y][new_state] > dists[x][y][state]:
                            dists[new_x][new_y][new_state] = dists[x][y][state]
                            queue.appendleft((new_x, new_y, new_state))
        else:
            d = state % 9
            d -= 1
            dx, dy = DIRECTIONS[d]
            new_x = dx + x
            new_y = dy + y
            if 0 <= new_x < H and 0 <= new_y < W:
                if S[new_x][new_y] == ".":
                    if dists[new_x][new_y][state] > dists[x][y][state]:
                        dists[new_x][new_y][state] = dists[x][y][state]
                        queue.appendleft((new_x, new_y, state))

            odd_even = state // 9
            new_state = (1 - odd_even) * 9
            if dists[x][y][new_state] > dists[x][y][state] + 1:
                dists[x][y][new_state] = dists[x][y][state] + 1
                queue.append((x, y, new_state))

    # 操作を行える？
    is_ok = False
    for dx, dy in DIRECTIONS:
        new_x = dx + sx
        new_y = dy + sy
        if 0 <= new_x < H and 0 <= new_y < W:
            if S[new_x][new_y] == ".":
                is_ok = True

    for gx, gy, t in queries:
        if not is_ok:
            print("No")
            continue

        ok = False
        for o in range(2):
            a = dists[gx][gy][o * 9]
            if a <= t and (t - a) % 2 == 0:
                ok = True
        if ok:
            print("Yes")
        else:
            print("No")

            


    

                
                        

        







if __name__ == "__main__":
    main()
0