結果

問題 No.2646 Cycle Maze
ユーザー LyricalMaestro
提出日時 2025-06-28 13:43:41
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,445 bytes
コンパイル時間 420 ms
コンパイル使用メモリ 82,384 KB
実行使用メモリ 370,652 KB
最終ジャッジ日時 2025-06-28 13:44:01
合計ジャッジ時間 19,815 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 43 TLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

from collections import deque

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):
        row = input()
        A.append([int(r) for r in row])
    
    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))
    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 ((1, 0), (-1, 0), (0, 1), (0, -1), (0, 0)):
            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 = A[new_h][new_w]
                    if (a - t - 1) % (a + 1) != 0:
                        dp1[new_hw_index] = True
                        queue.append((new_hw_index, t + 1))
    
    hw_index = to_hw_index(W, Gh - 1, Gw - 1)
    for t in range(T):
        if dp[t][hw_index]:
            print("Yes")
            return
    print("No")









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