結果

問題 No.2646 Cycle Maze
ユーザー LyricalMaestro
提出日時 2025-06-28 13:47:14
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,477 bytes
コンパイル時間 472 ms
コンパイル使用メモリ 82,404 KB
実行使用メモリ 351,536 KB
最終ジャッジ日時 2025-06-28 13:47:38
合計ジャッジ時間 21,882 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 47 TLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

from collections import deque

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

def to_hw_index(W, h, w):
    return h * W + w

def to_h_w(W, hw_index):
    return hw_index // W, hw_index % W

def main():
    H, W, T = map(int, input().split())
    Sh, Sw = map(int, input().split())
    Gh, Gw = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(input())
    
    dp = [[False] * (H * W) for _ in range(T)]
    dp[0][to_hw_index(W, Sh - 1, Sw - 1)]

    queue = deque()
    queue.append((to_hw_index(W, Sh - 1, Sw - 1), 0))
    g_hw_index = to_hw_index(W, Gh - 1, Gw - 1)
    while len(queue) > 0:
        hw_index, t = queue.popleft()
        if t + 1 >= T:
            continue

        dp1 = dp[t + 1 ]
        h, w = to_h_w(W, hw_index)
        for dh, dw in DIRECTIONS:
            new_h = h + dh
            new_w = w + dw
            if  0 <= new_h < H and 0 <= new_w < W and t + 1 < T:
                new_hw_index = to_hw_index(W, new_h, new_w)
                if not dp1[new_hw_index]:
                    a = int(A[new_h][new_w])
                    if (a - t - 1) % (a + 1) != 0:
                        dp1[new_hw_index] = True
                        queue.append((new_hw_index, t + 1))
                        if g_hw_index == new_hw_index:
                            print("Yes")
                            return
    
    print("No")









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