結果

問題 No.1638 Robot Maze
ユーザー lam6er
提出日時 2025-03-20 20:28:55
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,960 bytes
コンパイル時間 213 ms
コンパイル使用メモリ 82,656 KB
実行使用メモリ 83,912 KB
最終ジャッジ日時 2025-03-20 20:29:52
合計ジャッジ時間 6,526 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    H, W = map(int, input().split())
    U, D, R, L, K, P = map(int, input().split())
    x_s, y_s, x_t, y_t = map(int, input().split())
    start = (x_s - 1, y_s - 1)
    end = (x_t - 1, y_t - 1)
    grid = [input().strip() for _ in range(H)]
    
    total_at = sum(row.count('@') for row in grid)
    
    directions = [ (-1, 0, U), (1, 0, D), (0, 1, R), (0, -1, L) ]
    
    heap = []
    heapq.heappush(heap, (0, 0, start[0], start[1]))
    
    dist = [[dict() for _ in range(W)] for _ in range(H)]
    dist[start[0]][start[1]][0] = 0
    
    found = False
    
    while heap:
        current_cost, current_x, i, j = heapq.heappop(heap)
        
        if (i, j) == end:
            if current_cost <= K:
                found = True
                break
            continue
        
        if current_x not in dist[i][j] or dist[i][j][current_x] < current_cost:
            continue
        
        for di, dj, dir_cost in directions:
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W:
                cell = grid[ni][nj]
                
                if cell == '#':
                    continue
                
                new_x = current_x
                additional_cost = dir_cost
                
                if cell == '@':
                    new_x += 1
                    additional_cost += P
                
                if new_x > total_at:
                    continue
                
                new_cost = current_cost + additional_cost
                if new_cost > K:
                    continue
                
                if new_x in dist[ni][nj]:
                    if dist[ni][nj][new_x] <= new_cost:
                        continue
                
                dist[ni][nj][new_x] = new_cost
                heapq.heappush(heap, (new_cost, new_x, ni, nj))
    
    print("Yes" if found else "No")

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