結果

問題 No.2096 Rage With Our Friends
ユーザー lam6er
提出日時 2025-03-26 15:59:05
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,300 bytes
コンパイル時間 321 ms
コンパイル使用メモリ 82,496 KB
実行使用メモリ 209,204 KB
最終ジャッジ日時 2025-03-26 15:59:53
合計ジャッジ時間 9,482 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 WA * 2 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
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 for each y (1-based), a sorted list of x's (1-based) where grid[x-1][y-1] is '.'
    y_x_map = [[] for _ in range(W+1)]  # y_x_map[y] is list of x's sorted in increasing order
    for y in range(1, W+1):
        lst = []
        for x in range(1, H+1):
            if grid[x-1][y-1] == '.':
                lst.append(x)
        lst.sort()
        y_x_map[y] = lst
    
    # Initialize priority queue. Each element is (B, x, y, E)
    heap = []
    # To track max_E for each (x, y, B)
    max_E = [ [dict() for _ in range(W+1)] for _ in range(H+1) ]
    
    start_B = 0
    start_x = s_x
    start_y = s_y
    start_E = 0
    if start_x == g_x and start_y == g_y:
        print(0)
        return
    
    heapq.heappush(heap, (start_B, -start_E, start_x, start_y))
    max_E[start_x][start_y][start_B] = start_E
    
    found = False
    visited = set()
    
    while heap:
        current_B, neg_E, x, y = heapq.heappop(heap)
        current_E = -neg_E
        
        # Check if this state is the best possible
        if x == g_x and y == g_y:
            print(current_B)
            found = True
            break
        
        # Check if this state is outdated
        if current_B not in max_E[x][y] or max_E[x][y][current_B] > current_E:
            continue
        
        # Generate normal jump and boost jump
        for is_boost in [False, True]:
            if is_boost:
                x_max = x + 1 + current_E
            else:
                x_max = x + 1 + (current_E // 2)
            x_max = min(x_max, H)
            if x_max < 1:
                continue
            
            for dy in [-1, 1]:
                new_y = y + dy
                if new_y < 1 or new_y > W:
                    continue
                lst = y_x_map[new_y]
                if not lst:
                    continue
                
                # Find the largest x' <= x_max in lst
                idx_max = bisect.bisect_right(lst, x_max) -1
                if idx_max < 0:
                    continue
                new_x = lst[idx_max]
                if new_x < 1 or new_x > H:
                    continue
                
                new_E = max(0, x - new_x)
                new_B = current_B + (1 if is_boost else 0)
                
                # Check if new_B is already too high (some upper bound)
                if new_B > H + W:
                    continue
                
                # Check if this state is better than previously recorded
                if new_B in max_E[new_x][new_y]:
                    if max_E[new_x][new_y][new_B] >= new_E:
                        continue
                # Update and push to heap
                max_E[new_x][new_y][new_B] = new_E
                heapq.heappush(heap, (new_B, -new_E, new_x, new_y))
    
    if not found:
        print(-1)

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