結果
問題 | No.1638 Robot Maze |
ユーザー |
![]() |
提出日時 | 2021-08-06 21:56:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 146 ms / 2,000 ms |
コード長 | 1,406 bytes |
コンパイル時間 | 254 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 77,816 KB |
最終ジャッジ日時 | 2024-09-17 01:54:03 |
合計ジャッジ時間 | 5,132 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
import sys from heapq import heappop, heappush input = sys.stdin.readline h, w = map(int, input().split()) def idxtoxy(idx): return idx // w, idx % w def xytoidx(x, y): return x * w + y n = h * w U, D, R, L, K, P = map(int, input().split()) sx, sy, gx, gy = map(int, input().split()) graph = [list(input()) for _ in range(h)] dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] start = xytoidx(sx - 1, sy - 1) goal = xytoidx(gx - 1, gy - 1) cost = [D, R, U, L] def dijkstra(start, graph): infi = 1 << 80 mask = 1 << 18 pq = [] dist = [infi] * n heappush(pq, 0 * mask + start) while pq: temp = heappop(pq) d, v = temp // mask, temp & (mask - 1) if dist[v] <= d: continue if d > K: continue x, y = idxtoxy(v) dist[v] = d if v == goal: return dist[goal] for t in range(4): nx = x + dx[t] ny = y + dy[t] if 0 <= nx < h and 0 <= ny < w: delta = cost[t] if graph[nx][ny] == "#": continue if graph[nx][ny] == "@": delta += P u = xytoidx(nx, ny) nd = d + delta if dist[u] > nd: heappush(pq, nd * mask + u) return dist[goal] print("No" if dijkstra(start, graph) == 1 << 80 else "Yes")