a343. TOI 2021/12 潛力組：森林

題目描述

小明要在 N×M 的森林地圖中，從左上角 (0,0) 走到右下角 (N−1,M−1)。樹木不能進入，草地可以進入；起點與終點一定是草地。

開始時間是 0。每經過 1 單位時間，小明可以向上、下、左或右移動一格，也可以停留原地，但不能離開地圖。他必須在 T 單位時間內抵達終點。部分草地設有陷阱，陷阱只在指定時間區間內作用；每個整數時間 t（1 ≤ t ≤ T）完成移動或停留後，若所在格的陷阱正在作用，就損失該陷阱指定的生命值；停留在作用中的陷阱上也會在每個時間點再次扣血。求在期限內抵達終點的最小生命值損失。

輸入格式

第一行為 N、M、T、Q，分別是地圖列數、行數、時間限制與陷阱數。

• 2 ≤ N,M ≤ 200
• N+M−2 ≤ T ≤ 10^3
• 0 ≤ Q ≤ 10^5

接著 N 行，每行 M 個字元：0 表示草地，# 表示樹木。起點與終點保證可以進入。 接著 Q 行，每行為 H、W、S、E、A，表示座標 (H,W) 的陷阱在 S 到 E 時間作用（含兩端），在該時間點位於此格時損失 A 點生命值。

• 0 ≤ H ≤ N−1，0 ≤ W ≤ M−1
• 0 ≤ S ≤ E ≤ T
• 1 ≤ A ≤ 10^4

陷阱只位於起點、終點之外的草地。同一格草地上的陷阱不會在相同時間作用。

輸出格式

輸出一行整數，表示在 T 單位時間內到達終點的最小生命值損失。若無法在期限內抵達，輸出 -1。

原題分組限制

20 分：N≤10、T=N+M−2；20 分：T=N+M−2；15 分：Q=0；45 分：無額外限制。

範例 1

輸入：

5 6 10 5
00#000
000000
00#000
00#000
00#000
1 4 2 5 40
1 4 6 9 10
4 4 5 9 25
3 5 1 10 20
2 3 1 10 15

輸出：

30

範例 2

輸入：

5 6 10 0
00#000
00#000
00#000
00#000
00#000

輸出：

-1

範例 3

輸入：

5 6 9 5
00#000
000000
00#000
00#000
00#000
1 4 2 5 40
1 4 6 9 10
4 4 5 9 25
3 5 1 10 20
2 3 1 10 15

輸出：

35

範例 4

輸入：

5 6 11 5
00#000
000000
00#000
00#000
00#000
1 4 2 5 40
1 4 6 9 10
4 4 5 9 25
3 5 1 10 20
2 3 1 10 15

輸出：

10

原題疑義與審核備註

官方敘述中的示範路線把橘色陷阱損失寫成 15、總損失寫成 35；但同頁表格及範例輸入皆為橘色陷阱損失 10，範例 1 輸出 30。此處保留實際官方範例與陷阱數據，並註明原文敘述矛盾。

官方參考解答及詳解投影片的動態規劃轉移，包含停留原地，並在每個時間點加上所在格的陷阱傷害。因此此處已依官方補充來源明確寫出停留時也逐時間扣血。

來源

TOI 2021 年 12 月練習賽潛力組，依官方 PDF 整理。

官方原題：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202112/Forest.pdf

官方參考解答：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202112/Forest.zip

官方詳解投影片：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202112/Forest.odp

標籤：TOI 歷屆