n139. p11. 機器人出任務 - 高中生程式解題系統

內容

　　機器人 $\text{R2-D2}$ 正在一個棋盤格狀的地圖上移動並執行任務，地圖上會有些地方是 $\text{R2-D2}$ 無法越過的障礙物。$\text{R2-D2}$ 必需從起點出發並依序經過數個檢核點，最後到達終點才算完成任務。如下圖所示，$\text{R2-D2}$ 每一步可以向所在位子的八個方向任意移動，每一次移動都算走一步。請幫 $\text{R2-D2}$ 計算如果要成功完成任務，最少要移動的步數是幾步。給予的測試資料中，至少存在一條路徑來讓機器人完成任務。

輸入說明

　　第一行有兩個正整數，數字間以空格隔開，第一個數字是地圖橫軸格子數 $X$，第二個數字是地圖縱軸格子數 $Y$，且 $1\le X \le 200$, $1\le Y \le200$。最左上角的格子的座標為 $(x, y)=(0, 0)$。第二行只有一個數字 $N$ 且 $2\le N\le 10$，代表包括一個起點、數個檢核點（最少 $0$ 個、最多 $8$ 個）和一個終點，$\text{R2-D2}$ 共要依序經過多少地點。接下來的 $N$ 行，依序為一個起點、該經過的 $N-2$ 個檢核點還有一個終點座標。每一行有兩個數字，數字以空格格開，第一個數字為該點的橫軸座標，第二個數字是該點的縱軸座標。接下來有 $Y$ 行，每一行有 $X$ 個 $0$ 或 $1$ 的數字，並以空格格開，為地圖資料。$0$ 代表 $\text{R2-D2}$ 可以行走的區域，$1$ 代表 $\text{R2-D2}$ 不可行走的區域。

輸出說明

　　每筆測試資料的輸出只有一個正整數，代表完成這個任務所需的最少步數。

範例輸入 #1

10 10
4
4 0
2 3
4 9
9 6
0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 1 1 1 1 1 0 0 0 0
0 1 0 0 0 0 1 1 1 1
0 1 0 0 0 0 0 0 0 0
0 1 0 0 1 1 1 1 0 0
0 1 0 0 0 0 1 0 0 0
0 1 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0

範例輸出 #1

測資資訊：

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

提示：

2024/09/02 02:42 更正測資並重測全部程式碼

標籤:

BFS 最短路徑

出處:

110 新北市資訊學科能力複賽 [管理者： liaoweichen1024@gmail.com

liaoweichen1 ... (M_SQRT) ]

編號	身分	題目	主題	人氣	發表日期
43803	henry.rem.re ... (ฅ́˘ฅ̀)	n139	提醒 & 解題思路	38	2024-11-01 15:24
43802	henry.rem.re ... (ฅ́˘ฅ̀)	n139	提醒 & 解題思路	23	2024-11-01 15:24
43801	henry.rem.re ... (ฅ́˘ฅ̀)	n139	提醒 & 解題思路	26	2024-11-01 15:24
43800	henry.rem.re ... (ฅ́˘ฅ̀)	n139	提醒 & 解題思路	20	2024-11-01 15:24
43799	henry.rem.re ... (ฅ́˘ฅ̀)	n139	提醒 & 解題思路	21	2024-11-01 15:24