結果

問題 No.2096 Rage With Our Friends
コンテスト
ユーザー qwewe
提出日時 2025-04-24 12:30:51
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,136 bytes
コンパイル時間 425 ms
コンパイル使用メモリ 82,168 KB
実行使用メモリ 593,792 KB
最終ジャッジ日時 2025-04-24 12:32:04
合計ジャッジ時間 8,496 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 WA * 3 MLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    H = int(input[idx]); idx +=1
    W = int(input[idx]); idx +=1
    s_x = int(input[idx]); idx +=1
    s_y = int(input[idx]); idx +=1
    g_x = int(input[idx]); idx +=1
    g_y = int(input[idx]); idx +=1
    grid = []
    for _ in range(H):
        grid.append(input[idx])
        idx +=1
    
    # Precompute sorted_x for each column (1-based)
    sorted_x = [[] for _ in range(W+1)]  # columns 1..W
    for y in range(1, W+1):
        col = []
        for x in range(1, H+1):
            if grid[x-1][y-1] == '.':
                col.append(x)
        col.sort()
        sorted_x[y] = col
    
    # Initialize max_E: max_E[x][y] is a dictionary mapping k to max E
    max_E = [[dict() for _ in range(W+1)] for _ in range(H+1)]
    heap = []
    initial_k = 0
    initial_e = 0
    heapq.heappush(heap, (initial_k, -initial_e, s_x, s_y))
    max_E[s_x][s_y][initial_k] = initial_e
    
    found = False
    while heap:
        k, neg_e, x, y = heapq.heappop(heap)
        current_e = -neg_e
        
        # Check if this state is outdated
        if max_E[x][y].get(k, -1) > current_e:
            continue
        
        # Check if reached goal
        if x == g_x and y == g_y:
            print(k)
            found = True
            break
        
        # Generate possible moves
        for is_boost in [False, True]:
            new_k = k + (1 if is_boost else 0)
            # Calculate max_x based on jump type
            if is_boost:
                max_x_jump = x + 1 + current_e
            else:
                max_x_jump = x + 1 + (current_e // 2)
            actual_max_x = min(max_x_jump, H)
            
            for dy in [-1, 1]:
                new_y = y + dy
                if new_y < 1 or new_y > W:
                    continue
                
                # Find the largest x' <= actual_max_x in sorted_x[new_y]
                col = sorted_x[new_y]
                if not col:
                    continue
                # Binary search for the largest x' <= actual_max_x
                left, right = 0, len(col)-1
                best_x = -1
                while left <= right:
                    mid = (left + right) // 2
                    if col[mid] <= actual_max_x:
                        best_x = col[mid]
                        left = mid + 1
                    else:
                        right = mid - 1
                if best_x == -1:
                    continue
                new_x = best_x
                new_e = max(0, x - new_x)
                
                # Check if new_k is within possible bounds (H is upper limit)
                if new_k > H:
                    continue
                
                # Check if this new state is better
                current_max_e = max_E[new_x][new_y].get(new_k, -1)
                if new_e > current_max_e:
                    max_E[new_x][new_y][new_k] = new_e
                    heapq.heappush(heap, (new_k, -new_e, new_x, new_y))
    
    if not found:
        print(-1)

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