結果

問題 No.2096 Rage With Our Friends
ユーザー gew1fw
提出日時 2025-06-12 15:36:00
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,850 bytes
コンパイル時間 285 ms
コンパイル使用メモリ 82,704 KB
実行使用メモリ 484,468 KB
最終ジャッジ日時 2025-06-12 15:36:28
合計ジャッジ時間 7,245 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 TLE * 1 -- * 1
other -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    H = int(data[idx]); idx +=1
    W = int(data[idx]); idx +=1
    s_x = int(data[idx]); idx +=1
    s_y = int(data[idx]); idx +=1
    g_x = int(data[idx]); idx +=1
    g_y = int(data[idx]); idx +=1
    
    grid = []
    for _ in range(H):
        grid.append(data[idx])
        idx +=1
    
    # Preprocess row_map
    row_map = {}
    for y in range(1, W+1):
        row = []
        for x in range(1, H+1):
            if grid[x-1][y-1] == '.':
                row.append(x)
        row_map[y] = row
    
    # Initialize state: state[x][y] is a dictionary {c_boost: max_E}
    state = [ [ dict() for _ in range(W+1) ] for __ in range(H+1) ]
    state[s_x][s_y][0] = 0
    
    heap = []
    heapq.heappush(heap, (0, s_x, s_y, 0))
    
    found = False
    while heap:
        c_boost, x, y, e = heapq.heappop(heap)
        
        # Check if this state is outdated
        if c_boost not in state[x][y]:
            continue
        if state[x][y][c_boost] != e:
            continue
        
        # Check if goal is reached
        if x == g_x and y == g_y:
            print(c_boost)
            found = True
            break
        
        # Process normal jump
        x_max_normal = x + 1 + (e // 2)
        x_max_normal = min(x_max_normal, H)
        for dy in [-1, 1]:
            y_new = y + dy
            if 1 <= y_new <= W:
                row = row_map[y_new]
                if not row:
                    continue
                # Binary search for the maximum x' <= x_max_normal
                l, r = 0, len(row) -1
                res = -1
                while l <= r:
                    mid = (l + r) // 2
                    if row[mid] <= x_max_normal:
                        res = row[mid]
                        l = mid +1
                    else:
                        r = mid -1
                if res == -1:
                    continue
                x_new = res
                e_new = max(0, x - x_new)
                new_c = c_boost
                
                # Update state if better
                if new_c not in state[x_new][y_new]:
                    state[x_new][y_new][new_c] = e_new
                    heapq.heappush(heap, (new_c, x_new, y_new, e_new))
                else:
                    if e_new > state[x_new][y_new][new_c]:
                        state[x_new][y_new][new_c] = e_new
                        heapq.heappush(heap, (new_c, x_new, y_new, e_new))
        
        # Process boost jump
        x_max_boost = x + 1 + e
        x_max_boost = min(x_max_boost, H)
        for dy in [-1, 1]:
            y_new = y + dy
            if 1 <= y_new <= W:
                row = row_map[y_new]
                if not row:
                    continue
                l, r = 0, len(row) -1
                res = -1
                while l <= r:
                    mid = (l + r) // 2
                    if row[mid] <= x_max_boost:
                        res = row[mid]
                        l = mid +1
                    else:
                        r = mid -1
                if res == -1:
                    continue
                x_new = res
                e_new = max(0, x - x_new)
                new_c = c_boost + 1
                
                # Update state if better
                if new_c not in state[x_new][y_new]:
                    state[x_new][y_new][new_c] = e_new
                    heapq.heappush(heap, (new_c, x_new, y_new, e_new))
                else:
                    if e_new > state[x_new][y_new][new_c]:
                        state[x_new][y_new][new_c] = e_new
                        heapq.heappush(heap, (new_c, x_new, y_new, e_new))
    
    if not found:
        print(-1)

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