r637. P3. 迷霧森林中的救援隊 - 高中生程式解題系統

內容

森林被迷霧覆蓋，救援隊必須從入口到達安全屋。地圖是 R×C 的格子，格子上有通路、障礙、補給點（治癒包），還有會在每一步減少隊伍士氣的毒霧。隊伍有生命值 H0 初始值，穿越某些格子會扣血或補血（但血上限為 H）。救援隊允許在路上最多使用 K 次「跳躍」能力（每次可以移到曼哈頓距離 ≤ 2 的格子，花費 1 次跳躍），並且跳躍也會有血量消耗。請問在能否在不死亡下到達安全屋，並且最少步數為何？（若多種到達方式，取 minimal steps；若步數相同，取最大剩餘生命）

給 R,C 的格子，入口 S，出口 E。每格有整數影響 w[i][j]（可正可負，代表進入該格後 HP 改變，HP 維持在 0..H）。起點可在 S 上先套用影響（或視規格）。救援隊初始 HP = H0。允許最多 K 次跳躍（跳躍可到距離 ≤ 2 的任意格且不穿越牆，但目標格需非障礙），跳躍會花 1 跟普通移動一樣的「步數計數」。找出是否可到達 E，若可，輸出最少步數與在該步數下能達到的最大剩餘 HP；若不可則輸出 -1。

輸入說明

R C H0 K
（接下來 R 行，每行 C 個字元，描述地形：'.' 可走，'#' 障礙，'S' 起點， 'E' 終點）
（接下來 R 行，每行 C 個整數 w_ij）

1 ≤ R,C ≤ 50
1 ≤ H0 ≤ 200
0 ≤ K ≤ 20
-200 ≤ w_ij ≤ 200

輸出說明

若無解輸出 -1，否則輸出 步數 HP（步數最少、在最少步數的條件下 HP 最大）

範例輸入 #1

3 3 10 1
S..
##.
..E
0 -5 0
0 0 0
0 0 0

範例輸出 #1

3 10

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (4%): 1.0s , <1K
不公開測資點#1 (4%): 1.0s , <1K
不公開測資點#2 (4%): 1.0s , <1K
不公開測資點#3 (4%): 1.0s , <1K
不公開測資點#4 (4%): 1.0s , <1K
不公開測資點#5 (4%): 1.0s , <1K
不公開測資點#6 (4%): 1.0s , <1M
不公開測資點#7 (4%): 1.0s , <1K
不公開測資點#8 (4%): 1.0s , <1K
不公開測資點#9 (4%): 1.0s , <1K
不公開測資點#10 (6%): 1.0s , <1M
不公開測資點#11 (6%): 1.0s , <1M
不公開測資點#12 (6%): 1.0s , <1M
不公開測資點#13 (6%): 1.0s , <1K
不公開測資點#14 (6%): 1.0s , <1M
不公開測資點#15 (6%): 1.0s , <1M
不公開測資點#16 (6%): 1.0s , <1M
不公開測資點#17 (6%): 1.0s , <1K
不公開測資點#18 (6%): 1.0s , <1M
不公開測資點#19 (6%): 1.0s , <1K

提示：

(40%) R,C ≤ 30, K ≤ 5。
(60%) 原題範圍

標籤:

Algorithm Challenge contest Zaim

出處:

[管理者：

chenwei98050 ... (陳維（Z）) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」