結果

問題 No.3121 Prime Dance
コンテスト
ユーザー ts yi
提出日時 2025-04-20 18:47:26
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,323 bytes
コンパイル時間 516 ms
コンパイル使用メモリ 12,416 KB
実行使用メモリ 10,880 KB
最終ジャッジ日時 2025-04-20 18:47:29
合計ジャッジ時間 1,936 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 1 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
import sys

def main() -> None:
    sys.setrecursionlimit(1 << 25)
    input_data = sys.stdin.read().rstrip().splitlines()
    it = iter(input_data)

    H, W = map(int, next(it).split())
    Sy, Sx = map(int, next(it).split())   # 行, 列（1-indexed）
    Gy, Gx = map(int, next(it).split())   # 行, 列（1-indexed）

    Sy -= 1; Sx -= 1
    Gy -= 1; Gx -= 1

    grid = [list(next(it)) for _ in range(H)]

    DIRS  = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    MASKS = [1 << i for i in range(4)]

    INF = -1
    dist = [[[INF] * 16 for _ in range(W)] for _ in range(H)]
    dq = deque()

    start_state = 0
    dist[Sy][Sx][start_state] = 0
    dq.append((Sy, Sx, start_state))

    while dq:
        y, x, state = dq.popleft()
        d_now = dist[y][x][state]

        if (y, x) == (Gy, Gx) and state == 0:
            print(d_now)
            return

        for k, (dy, dx) in enumerate(DIRS):
            ny, nx = y + dy, x + dx
            if 0 <= ny < H and 0 <= nx < W and grid[ny][nx] != '#':
                nstate = state ^ MASKS[k]       # 対応するビットを反転
                if dist[ny][nx][nstate] == INF:
                    dist[ny][nx][nstate] = d_now + 1
                    dq.append((ny, nx, nstate))

    print(-1)

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