結果

問題 No.2096 Rage With Our Friends
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 15:31:05
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,284 bytes
コンパイル時間 332 ms
コンパイル使用メモリ 82,576 KB
実行使用メモリ 457,500 KB
最終ジャッジ日時 2025-06-12 15:32:38
合計ジャッジ時間 6,900 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 TLE * 1 -- * 1
other -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
from collections import defaultdict

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])-1; idx +=1  # 转换为0-based
    s_y = int(data[idx])-1; idx +=1
    g_x = int(data[idx])-1; idx +=1
    g_y = int(data[idx])-1; idx +=1
    S = []
    for _ in range(H):
        S.append(data[idx])
        idx +=1
    
    if S[s_x][s_y] != '.' or S[g_x][g_y] != '.':
        print(-1)
        return
    
    heap = []
    heapq.heappush(heap, (0, s_x, s_y, 0))  # (boosts, x, y, E)
    dp = defaultdict(lambda: defaultdict(dict))  # dp[x][y][boosts] = max_E
    dp[s_x][s_y][0] = 0
    
    found = False
    answer = -1
    
    while heap:
        boosts, x, y, E = heapq.heappop(heap)
        
        if x == g_x and y == g_y:
            answer = boosts
            found = True
            break
        
        # 处理通常跳跃
        max_x = x + 1 + (E // 2)
        max_x = min(max_x, H-1)
        for x_prime in range(0, max_x + 1):
            if x_prime < 0 or x_prime >= H:
                continue
            new_E = max(0, x - x_prime)
            for dy in [-1, 1]:
                y_prime = y + dy
                if 0 <= y_prime < W and S[x_prime][y_prime] == '.':
                    if new_E > dp[x_prime].get(y_prime, {}).get(boosts, -1):
                        dp[x_prime][y_prime][boosts] = new_E
                        heapq.heappush(heap, (boosts, x_prime, y_prime, new_E))
        
        # 处理助推跳跃
        max_x_boost = x + 1 + E
        max_x_boost = min(max_x_boost, H-1)
        for x_prime in range(0, max_x_boost + 1):
            if x_prime < 0 or x_prime >= H:
                continue
            new_E = max(0, x - x_prime)
            for dy in [-1, 1]:
                y_prime = y + dy
                if 0 <= y_prime < W and S[x_prime][y_prime] == '.':
                    if new_E > dp[x_prime].get(y_prime, {}).get(boosts +1, -1):
                        dp[x_prime][y_prime][boosts +1] = new_E
                        heapq.heappush(heap, (boosts +1, x_prime, y_prime, new_E))
    
    if found:
        print(answer)
    else:
        print(-1)

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