結果

問題 No.2096 Rage With Our Friends
ユーザー gew1fw
提出日時 2025-06-12 20:41:46
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,637 bytes
コンパイル時間 163 ms
コンパイル使用メモリ 81,664 KB
実行使用メモリ 533,268 KB
最終ジャッジ日時 2025-06-12 20:41:57
合計ジャッジ時間 7,125 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 MLE * 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 = []
    for _ in range(H):
        line = input().strip()
        grid.append([c == '.' for c in line])
    
    # Precompute farthest for each column
    farthest = [[0] * (H + 2) for _ in range(W + 2)]  # 1-based indexing
    for j in range(1, W + 1):
        current_max = 0
        for x in range(1, H + 1):
            if grid[x-1][j-1]:
                current_max = x
            farthest[j][x] = current_max
    
    max_E = [[dict() for _ in range(W + 2)] for _ in range(H + 2)]
    heap = []
    
    start_x, start_y = s_x, s_y
    start_k = 0
    start_E = 0
    max_E[start_x][start_y][start_k] = start_E
    heapq.heappush(heap, (start_k, -start_E, start_x, start_y))
    
    found = False
    while heap:
        current_k, neg_E, x, y = heapq.heappop(heap)
        current_E = -neg_E
        
        # Check if a better state was already processed
        if current_k in max_E[x][y] and max_E[x][y][current_k] > current_E:
            continue
        
        if x == g_x and y == g_y:
            print(current_k)
            found = True
            break
        
        # Explore both jump types
        for jump_type in ['normal', 'boost']:
            if jump_type == 'normal':
                x_max = x + 1 + (current_E // 2)
            else:
                x_max = x + 1 + current_E
            if x_max > H:
                x_max = H
            
            for dy in [-1, 1]:
                new_y = y + dy
                if new_y < 1 or new_y > W:
                    continue
                
                # Find the farthest x' <= x_max where grid[x'][new_y] is '.'
                max_x_prime = farthest[new_y][x_max]
                if max_x_prime == 0:
                    continue  # No such x' found
                
                new_E = max(0, x - max_x_prime)
                new_k = current_k + 1 if jump_type == 'boost' else current_k
                
                # Check if this state is better
                if new_k not in max_E[max_x_prime][new_y] or new_E > max_E[max_x_prime][new_y].get(new_k, -1):
                    if new_k not in max_E[max_x_prime][new_y]:
                        max_E[max_x_prime][new_y][new_k] = new_E
                    else:
                        if new_E > max_E[max_x_prime][new_y][new_k]:
                            max_E[max_x_prime][new_y][new_k] = new_E
                    heapq.heappush(heap, (new_k, -new_E, max_x_prime, new_y))
    
    if not found:
        print(-1)

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