結果

問題 No.2096 Rage With Our Friends
ユーザー gew1fw
提出日時 2025-06-12 20:41:32
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,602 bytes
コンパイル時間 147 ms
コンパイル使用メモリ 81,544 KB
実行使用メモリ 848,556 KB
最終ジャッジ日時 2025-06-12 20:41:36
合計ジャッジ時間 3,434 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 3 MLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    H = int(data[idx]); idx +=1
    W = int(data[idx]); idx +=1
    s_x = int(data[idx])-1; idx +=1
    s_y = int(data[idx])-1; idx +=1
    g_x = int(data[idx])-1; idx +=1
    g_y = int(data[idx])-1; idx +=1
    
    grid = []
    for _ in range(H):
        grid.append(data[idx])
        idx +=1
    
    INF = float('inf')
    max_k = H  # Since each boost jump increases k by 1, and H is up to 2000
    
    # Initialize max_e: max_e[k][x][y] = max_energy
    max_e = [[[-INF for _ in range(W)] for __ in range(H)] for ___ in range(max_k + 2)]
    max_e[0][s_x][s_y] = 0
    
    heap = []
    heapq.heappush(heap, (0, -0, s_x, s_y))  # (k, -E, x, y)
    
    found = False
    answer = -1
    
    while heap:
        current_k, current_neg_E, x, y = heapq.heappop(heap)
        current_E = -current_neg_E
        
        if x == g_x and y == g_y:
            answer = current_k
            found = True
            break
        
        if current_E < max_e[current_k][x][y]:
            continue  # a better state already processed
        
        # Process normal jumps
        x_max_normal = x + 1 + (current_E // 2)
        x_max_normal = min(x_max_normal, H-1)
        x_min_normal = 0
        for x_prime in range(x_min_normal, x_max_normal + 1):
            for dy in (-1, 1):
                new_y = y + dy
                if 0 <= new_y < W and grid[x_prime][new_y] == '.':
                    new_E = max(0, x - x_prime)
                    if new_E > max_e[current_k][x_prime][new_y]:
                        max_e[current_k][x_prime][new_y] = new_E
                        heapq.heappush(heap, (current_k, -new_E, x_prime, new_y))
        
        # Process boost jumps
        x_max_boost = x + 1 + current_E
        x_max_boost = min(x_max_boost, H-1)
        x_min_boost = 0
        for x_prime in range(x_min_boost, x_max_boost + 1):
            for dy in (-1, 1):
                new_y = y + dy
                if 0 <= new_y < W and grid[x_prime][new_y] == '.':
                    new_E = max(0, x - x_prime)
                    new_k = current_k + 1
                    if new_k > max_k:
                        continue  # We don't need to process beyond max_k
                    if new_E > max_e[new_k][x_prime][new_y]:
                        max_e[new_k][x_prime][new_y] = new_E
                        heapq.heappush(heap, (new_k, -new_E, x_prime, new_y))
    
    if found:
        print(answer)
    else:
        print(-1)

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