# APCS實作題2019年10月：傳送點
> 第1版：2024年8月20日
> 第2版：2025年1月7日，加上用陣列儲存待走訪佇列的另一種寫法
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=f166)
## 題目
### 問題描述
有 $n$ 個格子由左至右編號為 $0$ 到 $n−1$，皮卡丘的起始位置於編號 $0$ 的格子，想要走到編號 $P$ 的格子，每次他都可以往左走 $L$ 格或往右走 $R$ 格。
對於每個格子，都有一個對應的傳送點 $S$。在完成向左或向右的操作後，如果走到的格子為 $i$，皮卡丘將會瞬間被傳送到 $S(i)$，$S(i)$ 也有可能恰等於 $i$，即不傳送，此時 $i$ 被稱為停留點。其中起點和目標位置必為停留點，即 $S(0) = 0$、$S(P) = P$。
當傳送發生後，不能發生連續傳送的情況，也就是被傳送到 $S(i)$ 後，不會再次被傳送到 $S(S(i))$，
皮卡丘都必須在目前位置，再次選擇往左或往右走。需要注意的是，當走出表格外時，會被認定為出界，即不論是往左或往右或瞬間移動 $S(i)$，都不能夠走出表格外。
請問至少需要幾次操作，皮卡丘才能夠移動到 $P$；如果無解，則輸出 $-1$。
<br />
### 輸入說明
第一行包含四個整數 $n, P, L, R$，代表格子有 $n$ 格，目標位置 $P$ 和每次可以往左走 $L$ 格或往右走 $R$ 格，其中 $2 \leq n \leq 10^6,~0 \leq P \leq n-1,~1 \leq L, R \leq n/2$。
第二行有 $n$ 個數字，由左至右，表示每個格子的傳送點 $S(i)$，即 $S(0), S(1), \dots, S(n−1),~ |S(i)| ≤ 10^8$。
<br />
### 輸出格式
輸出跳躍到格子 $P$ 所需的最少操作數，若無法達成則輸出 $-1$。
<br />
### 範例輸入
```
5 3 1 2
0 2 4 3 1
```
### 範例輸出
```
2
```
<br /><br />
## Python 程式碼
### 寫法1，用串列儲存待走訪位置
費時最久約為 1 s，使用記憶體最多約為 113.2 MB，通過測試。
```python=
n, P, L, R = map(int, input().split()) # 讀取格數 n，終點 P，向左走格數 L，向右走格數 R
S = list(map(int, input().split())) # 讀取傳送點
steps = [-1]*n # 走到此格的步數，預設為 -1，代表還沒有走過
steps[0] = 0 # 原點步數為 0
st = [0] # 待走訪的串列，資料為位置
head = 0 # 由 st 讀取資料的索引值
while head < len(st) and steps[P] == -1: # 當 head 還沒有出界而且還沒有走到終點時繼續執行
x = st[head]; head += 1 # 由 st 讀取資料，將 head 加 1
cur = steps[x] # 現在這格的步數
for d in (-L, R): # 向左走 L 格，向右走 R 格
xn = x + d # 試著走訪的位置
# 如果 xn 及 S[xn] 沒有出界，而且 S[xn] 沒有走訪過
if xn >= 0 and xn < n and S[xn] >= 0 and S[xn] < n and steps[S[xn]] == -1:
steps[S[xn]] = cur + 1 # 最後停留的位置步數為 cur + 1
st.append(S[xn]) # 將 S[xn] 加入 st
print(steps[P]) # 印出終點對應的步數
```
<br />
也可以寫成這樣。
```python=
n, P, L, R = map(int, input().split())
S = list(map(int, input().split()))
que = [0]
head = 0
step = [-1]*n
step[0] = 0
while head < len(que) and que[head] != P:
u = que[head]; head += 1
for d in (-L, R):
v = u + d
if v < 0 or v >= n: continue
x = S[v]
if x < 0 or x >= n or step[x] >= 0: continue
step[x] = step[u] + 1
que.append(x)
print(step[P])
```
<br /><br />
### 寫法2，用 collections 函式庫中的雙向佇列儲存待走訪位置
費時最久約為 0.9 s，使用記憶體最多約為 113 MB，通過測試。
```python=
from collections import deque
n, P, L, R = map(int, input().split()) # 讀取格數 n，終點 P，向左走格數 L，向右走格數 R
S = list(map(int, input().split())) # 讀取傳送點
steps = [-1]*n # 走到此格的步數，預設為 -1，代表還沒有走過
steps[0] = 0 # 原點步數為 0
st = deque([0]) # 待走訪的雙向佇列，資料為位置
while st and steps[P] == -1: # 當 st 還有資料而且還沒有走到終點時繼續執行
x = st.popleft() # 移除 st 最左側的資料並指定給 x
cur = steps[x] # 現在這格的步數
for d in (-L, R): # 向左走 L 格，向右走 R 格
xn = x + d # 試著走訪的位置
# 如果 xn 及 S[xn] 沒有出界，而且 S[xn] 沒有走訪過
if xn >= 0 and xn < n and S[xn] >= 0 and S[xn] < n and steps[S[xn]] == -1:
steps[S[xn]] = cur + 1 # 最後停留的位置步數為 cur + 1
st.append(S[xn]) # 將 S[xn] 加入 st
print(steps[P]) # 印出終點對應的步數
```
<br /><br />
## C++ 程式碼
### 寫法1，用陣列儲存待走訪位置
費時最久約為 0.1 s，使用記憶體最多約為 8.6 MB，通過測試。
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0); // 加速
int n, P, L, R; cin >> n >> P >> L >> R; // 讀取格數 n，終點 P，向左走格數 L，向右走格數 R
vector<int> S (n); // 儲存傳送點的陣列
for(int i=0; i<n; i++) { // 執行 n 次
cin >> S[i]; // 讀取傳送點
if (S[i] < 0 || S[i] >= n) S[i] = n; // 傳送後會出界的位置，重設為 n，比較方便檢查是否出界
}
vector<int> steps (n, -1); // 走到此格的步數，預設為 -1，代表還沒有走過
steps[0] = 0; // 原點步數為 0
vector<int> st = {0}; // 待走訪的串列，資料為位置
int head = 0; // 由 st 讀取資料的索引值
int d[2] = {-L, R}; // 向左、向右走的格數
while(head < (int)st.size() && steps[P] == -1) { // 當 head 還沒有出界而且還沒有走到終點時繼續執行
int x = st[head]; head++; // 由 st 讀取資料，將 head 加 1
int cur = steps[x]; // 現在這格的步數
for(int i=0; i<2; i++) { // 向左走 L 格，向右走 R 格
int xn = x + d[i]; // 試著走訪的位置
if (xn >= 0 && xn < n && S[xn] != n && steps[S[xn]] == -1) { // 如果 xn 及 S[xn] 沒有出界，而且 S[xn] 沒有走訪過
steps[S[xn]] = cur + 1; // 最後停留的位置步數為 cur + 1
st.push_back(S[xn]); // 將 S[xn] 加入 st
}
}
}
cout << steps[P] << "\n"; // 印出終點對應的步數
return 0;
}
```
<br />
也可以寫成這樣。
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, P, L, R; cin >> n >> P >> L >> R;
vector<int> S (n);
for(int i=0; i<n; i++) cin >> S[i];
vector<int> step (n, -1), que = {0}, dx = {-L, R};
int head = 0; step[0] = 0;
while(head < (int)que.size() && step[P] == -1) {
int u = que[head]; head++;
for(int d : dx) {
int v = u + d;
if (v < 0 || v >= n) continue;
int x = S[v];
if (x < 0 || x >= n || step[x] != -1) continue;
step[x] = step[u] + 1;
que.push_back(x);
}
}
cout << step[P] << "\n";
return 0;
}
```
<br /><br />
### 寫法2，用佇列儲存待走訪位置
費時最久約為 0.1 s，使用記憶體最多約為 7.1 MB，通過測試。
```cpp=
#include <iostream>
#include <queue>
#include <cstring> // for memset
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0); // 加速
int n, P, L, R; cin >> n >> P >> L >> R; // 讀取格數 n，終點 P，向左走格數 L，向右走格數 R
int S[n]; // 儲存傳送點的陣列
for(int i=0; i<n; i++) { // 執行 n 次
cin >> S[i]; // 讀取傳送點
if (S[i] < 0 || S[i] >= n) S[i] = n; // 傳送後會出界的位置，重設為 n，比較方便檢查是否出界
}
int steps[n]; // 走到此格的步數
memset(steps, -1, sizeof(steps)); // 預設為 -1，代表還沒有走過
steps[0] = 0; // 原點步數為 0
queue<int> st; st.push(0); // 待走訪的串列，資料為位置，先放入原點 0
int d[2] = {-L, R}; // 向左、向右走的格數
while(!st.empty() && steps[P] == -1) { // 當 st 還資料而且還沒有走到終點時繼續執行
int x = st.front(); st.pop(); // 由 st 最前面讀取資料，再移除最前面的資料
int cur = steps[x]; // 現在這格的步數
for(int i=0; i<2; i++) { // 向左走 L 格，向右走 R 格
int xn = x + d[i]; // 試著走訪的位置
if (xn >= 0 && xn < n && S[xn] != n && steps[S[xn]] == -1) { // 如果 xn 及 S[xn] 沒有出界，而且 S[xn] 沒有走訪過
steps[S[xn]] = cur + 1; // 最後停留的位置步數為 cur + 1
st.push(S[xn]); // 將 S[xn] 加入 st
}
}
}
cout << steps[P] << "\n"; // 印出終點對應的步數
return 0;
}
```
<br /><br />
---
###### tags:`APCS`、`Python`、`C++`
Sign in with Wallet
Connect another wallet