結果

問題 No.2096 Rage With Our Friends
コンテスト
ユーザー qwewe
提出日時 2025-05-14 12:55:12
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,801 bytes
コンパイル時間 228 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 534,544 KB
最終ジャッジ日時 2025-05-14 12:55:50
合計ジャッジ時間 7,398 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 MLE * 1 -- * 1
other -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
import heapq

def main():
    H, W = map(int, input().split())
    s_x, s_y, g_x, g_y = map(int, input().split())
    grid = [input().strip() for _ in range(H)]
    
    # Precompute for each y (1-based), the sorted list of x's (1-based) where S[x][y] is '.'
    precomputed = [[] for _ in range(W + 2)]  # precomputed[y] for y in 1..W
    for y in range(1, W + 1):
        valid_x = []
        for x in range(1, H + 1):
            if grid[x-1][y-1] == '.':
                valid_x.append(x)
        precomputed[y] = valid_x
    
    # Initialize max_e: max_e[x][y] is a dictionary mapping boosts to the maximum E
    max_e = [[dict() for _ in range(W + 2)] for _ in range(H + 2)]
    heap = []
    heapq.heappush(heap, (0, s_x, s_y, 0))
    max_e[s_x][s_y][0] = 0
    
    while heap:
        boosts, x, y, e = heapq.heappop(heap)
        
        # Check if current state is the goal
        if x == g_x and y == g_y:
            print(boosts)
            return
        
        # Skip if this state is not the best possible for (x, y, boosts)
        current_max_e = max_e[x][y].get(boosts, -1)
        if e < current_max_e:
            continue
        
        # Generate possible jumps: normal and boost
        for jump_type in ['normal', 'boost']:
            if jump_type == 'normal':
                new_max_x = x + 1 + (e // 2)
            else:
                new_max_x = x + 1 + e
            new_max_x = min(new_max_x, H)
            
            # Check both directions: y-1 and y+1
            for dy in [-1, 1]:
                new_y = y + dy
                if new_y < 1 or new_y > W:
                    continue
                
                # Get the valid x's for new_y
                valid_x_list = precomputed[new_y]
                if not valid_x_list:
                    continue  # no valid x in this column
                
                # Find the largest x' <= new_max_x using binary search
                idx = bisect.bisect_right(valid_x_list, new_max_x) - 1
                if idx < 0:
                    continue
                x_prime = valid_x_list[idx]
                if x_prime < 1 or x_prime > H:
                    continue
                
                # Compute new_E and new_boosts
                new_E = max(0, x - x_prime)
                new_boosts = boosts + (1 if jump_type == 'boost' else 0)
                
                # Check if this new state is better than existing
                current_max_new_e = max_e[x_prime][new_y].get(new_boosts, -1)
                if new_E > current_max_new_e:
                    max_e[x_prime][new_y][new_boosts] = new_E
                    heapq.heappush(heap, (new_boosts, x_prime, new_y, new_E))
    
    # If no path found
    print(-1)

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