結果

問題 No.2096 Rage With Our Friends
コンテスト
ユーザー lam6er
提出日時 2025-04-09 21:02:54
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,380 bytes
コンパイル時間 160 ms
コンパイル使用メモリ 82,768 KB
実行使用メモリ 54,304 KB
最終ジャッジ日時 2025-04-09 21:05:02
合計ジャッジ時間 7,849 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 TLE * 1 -- * 1
other -- * 27
権限があれば一括ダウンロードができます

ソースコード

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
    
    # Preprocessing: for each column y (1-based), sorted list of x's where S[x][y] is '.'
    sorted_x = [[] for _ in range(W+2)]  # 1-based to W
    for y in range(1, W+1):
        lst = []
        for x in range(1, H+1):
            if grid[x-1][y-1] == '.':
                lst.append(x)
        sorted_x[y] = lst
    
    # Initialize max_e: a 2D array (x,y) of dictionaries, where key is k, value is max E.
    max_e = [[dict() for _ in range(W+2)] for __ in range(H+2)]  # x from 0 to H, y from 0 to W
    
    heap = []
    # Initial state: (k, E, x, y)
    heapq.heappush(heap, (0, 0, s_x, s_y))
    max_e[s_x][s_y][0] = 0
    
    found = False
    answer = -1
    while heap:
        current = heapq.heappop(heap)
        current_k = current[0]
        current_E = -current[1]
        current_x = current[2]
        current_y = current[3]
        
        # Check if this is the goal
        if current_x == g_x and current_y == g_y:
            answer = current_k
            found = True
            break
        
        # Check if this state is outdated (if a higher E already exists for this k)
        if current_k in max_e[current_x][current_y]:
            recorded_E = max_e[current_x][current_y][current_k]
            if recorded_E > current_E:
                continue
        else:
            continue
        
        # Generate possible moves for normal and boost jumps
        for jump_type in ['normal', 'boost']:
            if jump_type == 'normal':
                step = 1 + (current_E // 2)
                new_k = current_k
            else:
                step = 1 + current_E
                new_k = current_k + 1
            max_x_possible = current_x + step
            if max_x_possible > H:
                max_x_possible = H
            if max_x_possible < current_x:
                max_x_possible = current_x  # At least x current_x
            # Now, compute new x' for both directions (left and right)
            for dy in (-1, 1):
                new_y = current_y + dy
                if new_y < 1 or new_y > W:
                    continue
                possible_x_list = sorted_x[new_y]
                if not possible_x_list:
                    continue
                # Find the largest x' <= max_x_possible in possible_x_list
                idx_bisect = bisect.bisect_right(possible_x_list, max_x_possible) - 1
                if idx_bisect < 0:
                    continue
                new_x = possible_x_list[idx_bisect]
                new_E = max(0, current_x - new_x)
                # Check if new_x and new_y are valid (new_y is already valid)
                existing_e = max_e[new_x][new_y].get(new_k, -1)
                if new_E > existing_e:
                    max_e[new_x][new_y][new_k] = new_E
                    heapq.heappush(heap, (new_k, -new_E, new_x, new_y))
    
    if found:
        print(answer)
    else:
        print(-1)

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