結果
問題 |
No.1638 Robot Maze
|
ユーザー |
|
提出日時 | 2025-08-16 17:06:49 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 146 ms / 2,000 ms |
コード長 | 1,594 bytes |
コンパイル時間 | 329 ms |
コンパイル使用メモリ | 82,576 KB |
実行使用メモリ | 77,764 KB |
最終ジャッジ日時 | 2025-08-16 17:06:57 |
合計ジャッジ時間 | 6,606 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
## https://yukicoder.me/problems/no/1638 import heapq MAX_VALUE = 10 ** 18 def main(): H, W = map(int, input().split()) U, D, R, L, K, P = map(int, input().split()) s_x, s_y, t_x, t_y = map(int, input().split()) C = [] for _ in range(H): C.append(input()) DIRECTIONS = [(1, 0, D), (-1, 0, U), (0, 1, R), (0, -1, L)] s_x -= 1 s_y -= 1 t_x -= 1 t_y -= 1 queue = [] seen = [[MAX_VALUE] * W for _ in range(H)] fix = [[MAX_VALUE] * W for _ in range(H)] seen[s_x][s_y] = 0 heapq.heappush(queue, (0, s_x, s_y)) while len(queue) > 0: cost, x, y = heapq.heappop(queue) if fix[x][y] < MAX_VALUE: continue fix[x][y] = cost for dx, dy, c in DIRECTIONS: new_x = x + dx new_y = y + dy if 0 <= new_x < H and 0 <= new_y < W: if fix[new_x][new_y] < MAX_VALUE: continue if C[new_x][new_y] == "#": continue if C[new_x][new_y] == ".": new_cost = cost + c else: # 脆いかべ new_cost = cost + c + P if seen[new_x][new_y] > new_cost: seen[new_x][new_y] = new_cost heapq.heappush(queue, (new_cost, new_x, new_y)) if fix[t_x][t_y] == MAX_VALUE: print("No") else: if fix[t_x][t_y] <= K: print("Yes") else: print("No") if __name__ == "__main__": main()