結果

問題 No.1638 Robot Maze
ユーザー tktk_snsn
提出日時 2021-08-06 22:43:11
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 123 ms / 2,000 ms
コード長 871 bytes
コンパイル時間 362 ms
コンパイル使用メモリ 81,864 KB
実行使用メモリ 77,184 KB
最終ジャッジ日時 2024-09-17 02:55:10
合計ジャッジ時間 5,721 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff #

import heapq
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 18

H, W = map(int, input().split())
U, D, R, L, K, P = map(int, input().split())
xs, ys, xt, yt = map(lambda x: int(x)-1, input().split())
C = [input().rstrip() for _ in range(H)]

dydx4 = ((0, 1, R), (1, 0, D), (-1, 0, U), (0, -1, L))
dist = [[inf] * W for _ in range(H)]
dist[xs][ys] = 0

que = [(0, xs, ys)]
while que:
    ds, x, y = heapq.heappop(que)
    if dist[x][y] < ds:
        continue
    for dx, dy, dt in dydx4:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and C[nx][ny] != "#":
            cost = ds + dt + P * (C[nx][ny] == "@")
            if dist[nx][ny] > cost:
                dist[nx][ny] = cost
                heapq.heappush(que, (cost, nx, ny))

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