結果

問題 No.1638 Robot Maze
ユーザー Theta
提出日時 2024-04-16 18:51:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 175 ms / 2,000 ms
コード長 1,264 bytes
コンパイル時間 144 ms
コンパイル使用メモリ 82,392 KB
実行使用メモリ 78,552 KB
最終ジャッジ日時 2024-10-07 19:15:48
合計ジャッジ時間 6,256 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import heappop, heappush
from math import inf
DIJ = ((0, 1), (1, 0), (0, -1), (-1, 0))


def main():
    H, W = map(int, input().split())
    U, D, R, L, K, P = map(int, input().split())
    move_costs = (R, D, L, U)
    xs, ys, xt, yt = map(lambda n: int(n) - 1, input().split())
    board = [list(input()) for _ in range(H)]

    cost = [[inf for _ in range(W)] for _ in range(H)]
    cost[xs][ys] = 0
    queue = [(0, (xs, ys))]
    while queue:
        c_d, c_pos = heappop(queue)
        if c_d > cost[c_pos[0]][c_pos[1]]:
            continue
        for dij, m_cost in zip(DIJ, move_costs):
            n_pos = (c_pos[0] + dij[0], c_pos[1] + dij[1])
            if not (0 <= n_pos[0] < H and 0 <= n_pos[1] < W):
                continue
            if board[n_pos[0]][n_pos[1]] == "#":
                continue
            broken_cost = 0
            if board[n_pos[0]][n_pos[1]] == "@":
                broken_cost = P

            if cost[n_pos[0]][n_pos[1]] > c_d + m_cost + broken_cost:
                cost[n_pos[0]][n_pos[1]] = c_d + m_cost + broken_cost
                heappush(queue, (cost[n_pos[0]][n_pos[1]], n_pos))

    if cost[xt][yt] <= K:
        print("Yes")
    else:
        print("No")


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