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
17
測資資訊：
記憶體限制：
512
MB
提示 ：
2024/09/02 02:42 更正測資並重測全部程式碼
出處:
110新北市資訊學科能力複賽
[管理者：
liaoweichen1
...
(M_SQRT)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 43803 |
|
n139 | 33 | 2024-11-01 15:24 | |
| 43802 |
|
n139 | 19 | 2024-11-01 15:24 | |
| 43801 |
|
n139 | 23 | 2024-11-01 15:24 | |
| 43800 |
|
n139 | 19 | 2024-11-01 15:24 | |
| 43799 |
|
n139 | 19 | 2024-11-01 15:24 |