n139. p11. 機器人出任務
標籤 : BFS 最短路徑
通過比率 : 12人/15人 ( 80% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-09-02 02:47

內容

  機器人 $\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
17
測資資訊:
記憶體限制: 512 MB
提示 :

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

標籤:
BFS 最短路徑
出處:
110新北市資訊學科能力複賽 [管理者: liaoweichen1 ... (M_SQRT) ]

本題狀況 本題討論 排行

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