結果

問題 No.2096 Rage With Our Friends
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:21:12
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 4,162 bytes
コンパイル時間 393 ms
コンパイル使用メモリ 82,356 KB
実行使用メモリ 849,204 KB
最終ジャッジ日時 2025-05-14 13:23:41
合計ジャッジ時間 8,611 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 MLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

import collections

def solve():
    H, W = map(int, input().split())
    sx_orig, sy_orig, gx_orig, gy_orig = map(int, input().split())
    grid_str = [input() for _ in range(H)]

    start_x, start_y = sx_orig - 1, sy_orig - 1
    goal_x, goal_y = gx_orig - 1, gy_orig - 1

    q = collections.deque()
    
    # Using dict for sparse states: dist[(x,y,energy)] = min_boost_jumps
    dist = {} 
    
    # Initial state: (start_x, start_y, energy=0) with 0 boost jumps
    initial_state_key = (start_x, start_y, 0)
    dist[initial_state_key] = 0
    q.append(initial_state_key)

    min_boosts_to_goal = float('inf')

    while q:
        curr_x, curr_y, curr_E = q.popleft()
        current_b_count = dist[(curr_x, curr_y, curr_E)]

        # Pruning: If we already have a path to the goal that's better or equal
        # or if current path's boosts are already too high
        if current_b_count >= min_boosts_to_goal:
            continue

        # Moves: (is_boost_jump, cost_of_jump_type, jump_reach_bonus_E_factor)
        # jump_reach_bonus_E_factor: 0.5 for normal (floor(E/2)), 1 for boost (E)
        
        # Iterate Normal Jump then Boost Jump
        # For Normal Jump:
        max_x_prime_normal = curr_x + 1 + curr_E // 2
        # Iterate target_x from 0 up to min(H-1, max_x_prime_normal)
        for next_x_candidate in range(min(H, max_x_prime_normal + 1)): # Iterate x' from 0 up to max_x_prime_normal (inclusive)
            # next_x_candidate must be <= max_x_prime_normal, which is handled by loop range if max_x_prime_normal < H
            # And next_x_candidate must be >=0, also handled by loop range.
            
            new_b_count_normal = current_b_count # Cost 0
            
            # Pruning for normal jump (though cost is 0, useful if current_b_count is already high)
            if new_b_count_normal >= min_boosts_to_goal: # Unlikely to hit here if current_b_count was < min_boosts_to_goal
                pass # Allow to proceed because cost is 0

            next_E_val = max(0, curr_x - next_x_candidate)

            for dy_offset in [-1, 1]:
                next_y_candidate = curr_y + dy_offset
                if 0 <= next_y_candidate < W and \
                   0 <= next_x_candidate < H and \
                   grid_str[next_x_candidate][next_y_candidate] == '.':
                    
                    state_key = (next_x_candidate, next_y_candidate, next_E_val)
                    if new_b_count_normal < dist.get(state_key, float('inf')):
                        dist[state_key] = new_b_count_normal
                        q.appendleft(state_key) 
                        if next_x_candidate == goal_x and next_y_candidate == goal_y:
                            min_boosts_to_goal = min(min_boosts_to_goal, new_b_count_normal)
        
        # For Boost Jump:
        max_x_prime_boost = curr_x + 1 + curr_E
        new_b_count_boost = current_b_count + 1 # Cost 1

        # Pruning for boost jump
        if new_b_count_boost >= min_boosts_to_goal:
            continue # This path is already worse or equal

        # Iterate target_x from 0 up to min(H-1, max_x_prime_boost)
        for next_x_candidate in range(min(H, max_x_prime_boost + 1)):
            next_E_val = max(0, curr_x - next_x_candidate)

            for dy_offset in [-1, 1]:
                next_y_candidate = curr_y + dy_offset

                if 0 <= next_y_candidate < W and \
                   0 <= next_x_candidate < H and \
                   grid_str[next_x_candidate][next_y_candidate] == '.':
                    
                    state_key = (next_x_candidate, next_y_candidate, next_E_val)
                    if new_b_count_boost < dist.get(state_key, float('inf')):
                        dist[state_key] = new_b_count_boost
                        q.append(state_key)
                        if next_x_candidate == goal_x and next_y_candidate == goal_y:
                             min_boosts_to_goal = min(min_boosts_to_goal, new_b_count_boost)
                                
    if min_boosts_to_goal == float('inf'):
        print("-1")
    else:
        print(min_boosts_to_goal)

solve()
0