結果

問題 No.2096 Rage With Our Friends
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:41:34
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,422 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 82,000 KB
実行使用メモリ 55,584 KB
最終ジャッジ日時 2025-06-12 20:41:44
合計ジャッジ時間 7,652 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 TLE * 1 -- * 1
other -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

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 precomputed_left and precomputed_right
    precomputed_left = [[0] * (H + 1) for _ in range(W + 2)]  # [y][x_max]
    precomputed_right = [[0] * (H + 1) for _ in range(W + 2)]  # [y][x_max]
    
    for y in range(1, W + 1):
        # Precompute for left direction (y-1)
        y_new = y - 1
        if y_new >= 1:
            last = 0
            for x in range(1, H + 1):
                if grid[x - 1][y_new - 1] == '.':
                    last = x
                precomputed_left[y][x] = last
        # Precompute for right direction (y+1)
        y_new = y + 1
        if y_new <= W:
            last = 0
            for x in range(1, H + 1):
                if grid[x - 1][y_new - 1] == '.':
                    last = x
                precomputed_right[y][x] = last
    
    # Initialize the priority queue
    heap = []
    heapq.heappush(heap, (0, s_x, s_y, 0))
    
    # dist[x][y] is a dictionary mapping boost_count to max_e
    from collections import defaultdict
    dist = [[defaultdict(int) for _ in range(W + 1)] for _ in range(H + 1)]
    dist[s_x][s_y][0] = 0
    
    found = False
    answer = -1
    
    while heap:
        b, x, y, e = heapq.heappop(heap)
        
        # Check if current state is valid
        if x < 1 or x > H or y < 1 or y > W:
            continue
        if b not in dist[x][y] or dist[x][y][b] != e:
            continue
        
        if x == g_x and y == g_y:
            answer = b
            found = True
            break
        
        # Explore all possible moves
        for direction in ['left', 'right']:
            if direction == 'left':
                y_new = y - 1
                if y_new < 1:
                    continue
                # Use precomputed_left for current y
                y_target = y_new
                pre_arr = precomputed_left[y]
            else:
                y_new = y + 1
                if y_new > W:
                    continue
                y_target = y_new
                pre_arr = precomputed_right[y]
            
            # Try both normal and boost jumps
            for jump_type in ['normal', 'boost']:
                if jump_type == 'normal':
                    e_used = e // 2
                    x_max = x + 1 + e_used
                    if x_max > H:
                        x_max = H
                else:
                    e_used = e
                    x_max = x + 1 + e_used
                    if x_max > H:
                        x_max = H
                
                x_prime = pre_arr[x_max]
                if x_prime == 0:
                    continue
                
                new_e = max(0, x - x_prime)
                new_b = b + (1 if jump_type == 'boost' else 0)
                
                if x_prime < 1 or x_prime > H or y_new < 1 or y_new > W:
                    continue
                
                # Check if this state is better
                if new_b not in dist[x_prime][y_new] or new_e > dist[x_prime][y_new][new_b]:
                    dist[x_prime][y_new][new_b] = new_e
                    heapq.heappush(heap, (new_b, x_prime, y_new, new_e))
    
    if found:
        print(answer)
    else:
        print(-1)

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