結果

問題 No.2096 Rage With Our Friends
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 15:30:56
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,121 bytes
コンパイル時間 366 ms
コンパイル使用メモリ 82,220 KB
実行使用メモリ 849,460 KB
最終ジャッジ日時 2025-06-12 15:32:31
合計ジャッジ時間 3,678 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 WA * 2 MLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import heapq

def main():
    H, W = map(int, sys.stdin.readline().split())
    s_x, s_y, g_x, g_y = map(int, sys.stdin.readline().split())
    grid = []
    for _ in range(H):
        grid.append(sys.stdin.readline().strip())
    
    valid = [[False]*(W+2) for _ in range(H+2)]
    for x in range(1, H+1):
        for y in range(1, W+1):
            if grid[x-1][y-1] == '.':
                valid[x][y] = True
    
    max_boosts = H * 2  # 一个估计值，实际可能更小
    dp = [[[-1]*(max_boosts +1) for _ in range(W+2)] for __ in range(H+2)]
    heap = []
    
    dp[s_x][s_y][0] = 0
    heapq.heappush(heap, (0, s_x, s_y, 0))
    
    dirs = [-1, 1]
    found = False
    answer = -1
    
    while heap:
        boosts, x, y, e = heapq.heappop(heap)
        
        if x == g_x and y == g_y:
            answer = boosts
            found = True
            break
        
        if boosts > max_boosts:
            continue
        
        # 通常跳跃
        max_x = x + 1 + (e // 2)
        x_high = min(max_x, H)
        x_low = 1
        for dx in range(x_high, x_low-1, -1):
            for dy_dir in dirs:
                ny = y + dy_dir
                if 1 <= ny <= W and valid[dx][ny]:
                    new_e = max(0, x - dx)
                    if dp[dx][ny][boosts] < new_e:
                        dp[dx][ny][boosts] = new_e
                        heapq.heappush(heap, (boosts, dx, ny, new_e))
        
        # Boost跳跃
        max_x_boost = x + 1 + e
        x_high_boost = min(max_x_boost, H)
        for dx in range(x_high_boost, x_low-1, -1):
            for dy_dir in dirs:
                ny = y + dy_dir
                if 1 <= ny <= W and valid[dx][ny]:
                    new_e_boost = max(0, x - dx)
                    if boosts + 1 > max_boosts:
                        continue
                    if dp[dx][ny][boosts+1] < new_e_boost:
                        dp[dx][ny][boosts+1] = new_e_boost
                        heapq.heappush(heap, (boosts+1, dx, ny, new_e_boost))
    
    print(answer if found else -1)

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