a345. TOI 2020/11 潛力組：遊戲地圖

題目描述

小華在地牢遊戲中要從起點走到終點。地圖上有障礙與陷阱；玩家起始只有 3 點血量，每走過一次陷阱便扣 1 點，血量降為 0 就失敗。每一步可以向上、下、左或右移動一格，不能超出地圖，也不能進入障礙格。每次進入陷阱格都會扣血，即使先前已走過同一陷阱也一樣。請求出能成功到達終點的最少步數。

輸入格式

第一行為 x、y，表示地圖橫向與縱向寬度，1 < x,y < 1000。 第二行為起點 Sx、Sy，第三行為終點 Ex、Ey。左下角為 (0,0)，保證起點與終點在地圖上。 第四行為 B、T，分別表示障礙與陷阱數。 接著 B 行，每行為 BX_i、BY_i，表示障礙座標。最後 T 行，每行為 TX_i、TY_i，表示陷阱座標。同一行整數以空白分隔。

輸出格式

輸出成功路徑的最少步數；若不存在成功路徑，輸出 -1。

原題分組限制

25 分：沒有陷阱；25 分：沒有障礙物；50 分：無額外限制。

範例 1

輸入：

3 5
0 4
0 0
4 0
1 1
1 2
0 3
1 3

輸出：

8

範例 2

輸入：

3 3
2 0
0 2
2 0
1 0
1 1

輸出：

4

原題疑義與審核備註

上下左右四方向移動、不得越界或進入障礙，以及每次進入陷阱都扣血，已由官方參考解答確認。官方原題仍未給 B、T 的數值上限，也未明定障礙與陷阱重疊規則或起終點是否可能含陷阱；此處不自行增加這些保證。

來源

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

官方原題：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202011/Game%20Map.pdf

官方參考解答：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202011/Game%20Map.zip

官方詳解投影片：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202011/Game%20Map.odp

標籤：TOI 歷屆