# 2023/06 APCS 實作題
開始之前先宣傳一下[我的IG](https://www.instagram.com/apcser_code_teacher/)，裡面有演算法的介紹，各類題目的講解跟其他有助升學的資料
## 1. 路徑偵測
[題目連結](https://zerojudge.tw/ShowProblem?problemid=k731)
題目敘述 :
給一個二維平面，座標如同數學的二維座標(Ｙ正為北，Ｘ正為東)
起始位置在 $( 0 , 0 )$ ，接下來會有 $N$ 個座標，你需要按照這些座標點的順序移動
保證僅會垂直或水平方向上移動，**不會斜向移動**，且第一個點保證一定是Ｘ軸正的位置(初始方向向右)
請輸出這條路徑中，左轉、右轉、迴轉的個數分別為多少
輸出說明 :
第一行輸入一個正整數 $n$ ，接下來有 $n$ 行，每一行都有兩個正整數 $x , y$
保證相鄰兩個點的座標差值不超過 100
輸出說明 :
輸出三個正整數，分別代表左轉、右轉、迴轉的次數
解題思路 :
這題用多個 if 加上 for 迴圈可以解，但是在教學的角度還是希望各位學習**數字表示方向**的方式
利用數字表示方向的方式就是使用 0 1 2 3 代表 北 東 南 西
當我現在的方向是"東"時，我往左右分別是北跟南，迴轉就是西
如果用數字表現就是 **東 : 1 ,北 : 0 ,南 : 2 ,西 : 3**
也就是說(新的方向-舊的方向) == 1就是左轉，2就是迴轉，-3就是右轉
在這個例子當中，**會出現負數的情況**，對於處理負數的方式我們可以採用下述的方式 :
```python=
# new_go 新的方向, before_go 舊的方向, turn 轉彎方向
turn = (new_go - before_go + 4) % 4
```
透過這種方式就可以將負數變成0~3的正整數
(python其實不需要+4的處理，但為了教學還是加進去)
再來列出本題要注意的點
1. 不會斜向移動(只會 $\pm x$ 或是 $\pm y$ )
2. 初始方向向右(東)
3. Ｙ正為北，Ｘ正為東
4. 起始位置在( 0 , 0 )，但初始方向已經訂好了
5. 依序輸出三個正整數(左轉、右轉、迴轉)
這幾個細節都要**兼顧到**才能寫出對的程式碼
搞不好你會題目，卻被這種小細節弄到丟了某些分數，也是沒必要的失誤
再來解題的部分很簡單，為了完全沒學過程式碼(剛接觸)的初學者
我會介紹**第一子題**的方式，子題一的 $n == 2$
也就是說完全不需要用到 for 迴圈，因為第一個方向固定是東(不算是轉彎)
所以我們只要知道第二個方向是面向哪裡就知道答案了
至於判斷方向的方式，有說過**Ｙ正為北，Ｘ正為東**，也就是說
如果現在的 $x$ 比前一個大，**方向就向北**，如果現在的 $y$ 比前一個大，**方向就向東**
其他就以此類推，我們可以得到下面的判斷方式 :
* $new\_x > before\_x$ : 向東(數字表示: 1)
* $new\_x < before\_x$ : 向西(數字表示: 3)
* $new\_y > before\_y$ : 向北(數字表示: 0)
* $new\_y < before\_y$ : 向南(數字表示: 2)
程式碼如下 :
```python=
left, right, turn_back = 0, 0, 0
# 依序代表左轉，右轉，迴轉 三者的次數
n = int(input()) # 輸入 n
before_x, before_y = map(int, input().split())
# 輸入第一個座標
new_x, new_y = map(int, input().split())
# 輸入第二個座標
# 因為 new_x > before_x 還是往東走，所以不用判斷
if new_y > before_y : # 往北
left += 1
elif new_y < before_y : # 往南
right += 1
elif new_x < before_x : # 往西
turn_back += 1
print(left,right,turn_back) # 輸出答案
```
再來第二子題就要加上我之前介紹的方向數字化還有for迴圈
```python=
left, right, turn_back = 0, 0, 0
# 依序代表左轉，右轉，迴轉 三者的次數
before_go = 1 # 行進方向(開始為東方)
n = int(input()) # 輸入 n
before_x, before_y = map(int, input().split())
# 輸入第一個座標
for i in range(0,n-1,1) :
new_x, new_y = map(int, input().split())
# 輸入第 2-n 個座標
if new_y > before_y : # 往北
new_go = 0
elif new_y < before_y : # 往南
new_go = 2
elif new_x > before_x : # 往東
new_go = 1
elif new_x < before_x : # 往西
new_go = 3
# 處理負數
turn = (new_go - before_go + 4) % 4
if turn == 1 :
right += 1
elif turn == 2 :
turn_back += 1
elif turn == 3 :
left += 1
# 換成新的方向跟座標
before_go = new_go
before_x, before_y = new_x, new_y
print(left,right,turn_back) # 輸出答案
```
## 2. 特殊位置
(我會依照演算法的難度講解各種方式)
[題目連結](https://zerojudge.tw/ShowProblem?problemid=k732)
題目敘述 :
給定一個 $n×m$ 的二維矩陣 $a$，設 $x = a[i][j]$
離 $(i,j)$ 曼哈頓距離為$x$內的點數值總和 % 10 恰為$x$的點稱之為特殊位置
定義兩個點 $(a,b)$ 和 $(c,d)$ 的曼哈頓距離為 $|a - c| + |b - d|$
請寫一個程式，輸出共有幾個特殊位置，並按照字典序由小到大輸出這些位置的座標
輸入說明 :
第一行輸入兩個正整數 $n,m$ ，接下來有 $n$ 行，每行有 $m$ 個數字，每一個數字介於 $0$ 到 $9$
輸出說明 :
第一行輸出共有幾個特殊位置，接下來輸出 $k$ 行
每一行輸出"兩個正整數"代表坐標點位
特殊位置請按照字典順序由小到大輸出
### 第一子題
第一子題的要求是 $n == 1$ ，也就是**一維陣列**
因為不需要考慮上下的點，所以程式碼用兩個for迴圈就可以處理了
在跑左右的時候，根據上面的圖形，我們假設現在是$a[i]$，範圍就是$[\ i-a[\ i\ ] , i+a[\ i\ ]\ ]$
而且如果 $i - a[\ i\ ] < 0$ 或 $i + a[\ i\ ] >= m$ 也不在矩陣範圍，所以我們可以先做處理
```python=
# 定義範圍
si = i - a[i]
se = i + a[i]
# 處理
if si < 0 :
si = 0
if se >= m :
se = m - 1
```
最後就只要用一層 for 迴圈跑過整個矩陣，再用另外一個 for 迴圈跑過定義的範圍去**計算總合**
```python=
# 輸入測資
n, m = map(int, input().split())
a = list(map(int, input().split()))
# n, m = 1, 8
# a = [1, 2, 3, 4, 5, 6, 7, 8]
anses = []
for i in range(m) :
tmp = 0 # 範圍總和
# 定義範圍
si = i - a[i]
se = i + a[i]
# 處理
if si < 0 :
si = 0
if se >= m :
se = m - 1
# 跑範圍
for j in range(si,se+1,1) :
tmp += a[j]
# 判斷是否是特殊位置
if tmp % 10 == a[i] % 10 :
anses.append((0,i))
print(len(anses)) # 輸出座標個數
for i in anses :
print(*i) # 輸出各個座標
```
接下來介紹的方式都是針對第二子題
### 正方形
雖然上方的題目要求是**菱形**，但是在考試中可能無法想到規律跑出的辦法，所以我們直接將空白地方補齊，**變成一整個正方形**
解題思路 :
由上圖我們發現
當 $a[\ i\ ][\ j\ ] == 1$ 時，會得到 $3 × 3$ 的正方形
當 $a[\ i\ ][\ j\ ] == 2$ 時，會得到 $5 × 5$ 的正方形
由上兩者整理出規律為 :當 $a[\ i\ ][\ j\ ] == dis$ 時，會得到 $(2dis+1) × (2dis+1)$ 的正方形
也就是說列的範圍是 $(i-dis)$ 到 $(i+dis)$ ，行的部份一樣是 $(j-dis)$ 到 $(j+dis)$ (直行橫列)
```python=
si, ei = i - dis, i + dis
sj, ej = j - dis, j + dis
```
因為只能跑矩陣內的範圍
所以 $si, sj < 0$ 或 $ei >= n$ 或 $ej >= m$ 時也不能算進去
用 if 判斷作處理把兩者做**下限**跟**上限**
最後就可以跑正方形了
```python=
def find_all(dis,x,y) : # 跑正方形
tmp = 0 # 儲存範圍內的總合
si, ei = x-dis, x+dis # 定義i的範圍
# 做上限下限
if si < 0 :
si = 0
if ei >= n :
ei = n - 1
# 跑正方形範圍
for i in range(si,ei+1) :
sj, ej = y-dis, y+dis # 定義j的範圍
# 做上限下限
if sj < 0 :
sj = 0
if ej >= m :
ej = m - 1
for j in range(sj,ej+1) :
# 在曼哈頓距離內才+
if abs(x-i)+abs(y-j)<=dis :
tmp += l[i][j]
# 判斷是否為特殊位置
if tmp % 10 == dis % 10 :
return True
return False
```
最後加上主程式碼就可以了
```python=
# 輸入測資
n, m = map(int, input().split())
l = [list(map(int, input().split())) \
for i in range(n)]
anses = [] # 存放答案座標
for i in range(n) :
for j in range(m) :
if find_all(l[i][j],i,j) :
anses.append((i,j))
print(len(anses)) # 座標個數
for i in anses :
print(*i) # 輸出各個座標
```
結論 : 這個解法在ZJ上的時間是0.3s，因為這是**列舉的方式**，所以才會耗費這麼久的時間，稍微預估一下就可以知道了
### 規律解
上圖增加了 $i$ 的範圍，因為本次的規律解是修改 $j$ 的範圍
至於修改範圍的方式，一樣是**先定義在判斷**，首先假設要判斷的點為 $a[\ x\ ][\ y\ ]$ 且 $dis = a[\ x\ ][\ y\ ]$
如果仔細觀察會發現，當你在任何一點 $(ti,tj)$ 時，$j$ 的左右兩邊都少了 $\mid ti-x \mid$ 格
比如你在 $-1$ 列， $j$ 的左右兩邊都少了 $\mid -1 \mid$ 格
也就是說 $tj$ 的範圍會變成$[\ y-dis+1 ,\ y+dis-1\ ]$
最後得出規律 :
在 $ti$ 行時，$tj$ 的範圍是 $(\ y-dis\ +\mid ti-x \mid ,\ y+dis\ -\mid ti-x \mid\ )$
這樣可能還是有點抽象，所以我們用程式的方式表現
```python=
si, ei = x-dis, x+dis # 定義i的範圍
# 做上限下限
if si < 0 :
si = 0
if ei >= n :
ei = n - 1
# 跑菱形範圍
for i in range(si,ei+1) :
# 定義j的範圍
sj, ej = y - dis + abs(i-x), y + dis - abs(i-x)
```
然後再做判斷處理
```python=
sj, ej = y - dis + abs(i-x), y + dis - abs(i-x)
# 做上限下限
if sj < 0 :
sj = 0
if ej >= m :
ej = m - 1
```
最後加上其他部分跟主程式就可以了
```python=
def find_all(dis,x,y) : # 跑距離
tmp = 0 # 儲存範圍內的總合
si, ei = x-dis, x+dis # 定義i的範圍
# 做上限下限
if si < 0 :
si = 0
if ei >= n :
ei = n - 1
# 跑正方形範圍
for i in range(si,ei+1) :
# 定義j的範圍
sj, ej = y - dis + abs(i-x), y + dis - abs(i-x)
# 做上限下限
if sj < 0 :
sj = 0
if ej >= m :
ej = m - 1
for j in range(sj,ej+1) :
tmp += a[i][j]
if tmp % 10 == dis % 10 :
return True
return False
# 輸入測資
n, m = map(int, input().split())
l = [list(map(int, input().split())) \
for i in range(n)]
anses = [] # 存放答案座標
for i in range(n) :
for j in range(m) :
if find_all(l[i][j],i,j) :
anses.append((i,j))
print(len(anses)) # 座標個數
for i in anses :
print(*i) # 輸出各個座標
```
結論 : 這個解法在ZJ上的時間是78ms，因為這是相比於列舉的方式，減少了許多不必要的地方，所以才能快這麼多
### BFS
這個題目完全不適合用BFS，我的方式也是針對題目做變形，對於學習沒有幫助，所以只放程式碼
```python=
from collections import deque
n, m = map(int, input().split())
l = [list(map(int, input().split())) \
for i in range(n)]
# n, m = 2, 3
# l = [[5, 2, 3],
# [4, 5, 6],]
mm = [(0,1),(0,-1),(1,0),(-1,0)]
anses = []
gone = [[True] * m for i in range(n)]
for i in range(n) :
for j in range(m) :
has = [(i,j)]
dis = l[i][j]
tmp = 0
queue = deque([(i,j)])
while queue :
x, y = queue.pop()
now = l[x][y]
gone[x][y] = False
tmp += now
for px, py in mm :
nx = x + px
ny = y - py
if 0<=nx<n and 0<=ny<m :
if gone[nx][ny] and \
abs(nx-i) + abs(ny-j) <= dis :
queue.append((nx,ny))
has.append((nx,ny))
gone[nx][ny] = False
for c,v in has :
gone[c][v] = True
if (tmp-dis) % 10 == 0 :
anses.append((i,j))
print(len(anses))
for i in anses :
print(*i)
```
### 前綴和
前綴和的方式其實也算是**規律解的進階版**，如果你已經學過前綴和，那你應該能很快理解
如果你還沒學過，可以去看我寫的教學[前綴和(prefix sum)](https://hackmd.io/@apcser/ByNGmazhs)
我們先假設前綴和的陣列是 $acc$，$j$ 的範圍是 $(\ sj\ ,\ ej \ )$
在上面的例子中，我們有說 $j$ 的範圍是多少，但其實如果使用前綴和去解釋
那 $j$ 範圍總和其實就是 $acc[\ i\ ][\ ej\ ] - acc[\ i\ ][\ sj\ ]$
不過你應該可以發現，如果我要的值 $sj\ ==\ ej$，會導致**值相減**變成 $0$
所以我們可以在前綴和的陣列前面加上一個 $0$，並把範圍總和修改成 $acc[\ i\ ][\ ej+1\ ] - acc[\ i\ ][\ sj\ ]$
就可以解決這個問題了，至於其他的部分都跟規律解相似，我就不贅述了
```python=
def find_all(dis,x,y) : # 跑距離
tmp = 0 # 儲存範圍內的總合
si, ei = x-dis, x+dis # 定義i的範圍
# 做上限下限
if si < 0 :
si = 0
if ei >= n :
ei = n - 1
# 跑菱形範圍
for i in range(si,ei+1) :
# 定義j的範圍
sj, ej = y - dis + abs(i-x), y + dis - abs(i-x)
# 做上限下限
if sj < 0 :
sj = 0
if ej >= m :
ej = m - 1
tmp += acc[i][ej+1] - acc[i][sj]
# 判斷是否為特殊位置
if tmp % 10 == dis % 10 :
return True
return False
# 輸入測資
n, m = map(int, input().split())
a = []
acc = [] # 前綴和陣列
for i in range(n) :
# 輸入測資
# a.append(list(map(int, input().split())))
acc.append([0]) # 先加入 0
count = 0
# 計算前綴和
for j in range(m) :
count += a[i][j]
acc[i].append(count)
anses = [] # 存放答案座標
for i in range(n) :
for j in range(m) :
if find_all(a[i][j],i,j) :
anses.append((i,j))
print(len(anses))
for i in anses :
print(*i)
```
結論 : 這個解法在ZJ上的時間是46ms，因為這是相比於規律解的方式，減少了 $j$ 的範圍
不過因為前綴和的處理也要時間，所以相較之前的時間變化不大
## 3. 磁軌移動序列
[題目連結](https://zerojudge.tw/ShowProblem?problemid=k733)
題目敘述 :
你拿到一個磁帶和一串指令，磁帶上的指針初始位置為 $10$，我們將其表示為 $T10$
指令是一個由多個 $T$ 和 loop 指令組成的字串，**每個指令都會影響指針的移動**
$T$ 指令的格式為 $Tx$，其中 $x$ 是兩位數的整數（10~99），代表指針從當前位置移動到 $x$
除了 $T$ 指令外，還有一個 loop 指令結構，其格式為 Ly...E，其中 $y$ 是一位數的整數（1~9）
loop 指令允許重複執行一系列指令，loop 指令的開始標記為 $Ly$，結束標記為 $E$
指令序列位於這兩個標記之間，$Ly$ 和 $E$ 中間的指令會被重複執行
loop 指令可以嵌套，也就是說，**一個 loop 指令的內部可以包含其他的 loop 指令**
保證所有 loop 指令內一定會有**至少一個 T 指令**
請寫一個程式，根據給定的指令串，**計算指針總共移動的距離**
範例： 給定指令串：T10T15T23T23T22T22T44 指針總共移動的距離為：5 + 8 + 0 + 1 + 0 + 22 = 36
此題和 APCS 原題的差異是 Loop 迴圈的值域是 (2~9), 由於不影響整體的解題策略, 因此不做修改僅註記與此
輸入說明 :
輸入一個字串，為該磁帶指針的控制指令
輸出說明 :
輸出一個正整數，代表指針執行完指令後所移動的總路徑長
例如 : T10T15T23T23T22T22T44
$\mid\ 15-10\mid +\ \mid 23-15\ \mid +\ \mid 23-23\ \mid +\ \mid 22-23\ \mid +\ \mid 22-22\ \mid +\ \mid 44-22\ \mid$
### 第一子題
第一子題沒有loop的存在，所以我們可以用split速解
不過在教學的角度，肯定是不希望用這種偷吃步的辦法
(如果你還是想知道，可以私訊[我的IG](https://www.instagram.com/apcser_code_teacher/))
第一子題只佔10分，只能算是稍微補齊之前沒拿到的分數
首先要抓到題目的重點
1. 開頭必定是T10
2. 如果遇到 $T$，$T$ 後面的兩位數字是新的位置
3. 移動距離是 $\mid new\_x-x\mid$
4. 答案是移動距離總和
有這三個認知就能開始解題了，首先我們要定義兩個變數 $new\_x,x$ 去儲存**當前位置跟前一個位置**
跑過整個字串，判斷有沒有遇到 $T$
然後透過第三個重點的計算方式算出**移動距離總和**
最後輸出答案就好了
其實可以完全省略判斷 $T$ 的部分，但是為了更好的銜接第二子題
我還是把判斷 $s[idx]$ 是否為 $T$ 放進去
```python=
s = input()
idx = 3
x = 10
new_x = 0
ans = 0
while idx < len(s) :
# 判斷s[idx]是否為 T
if s[idx] == "T" :
idx = idx+1 # 將idx移動到數字的第一位
# 新的數字
new_x = int(s[idx:idx+2])
# 計算距離
ans += abs(new_x - x)
# 移動到下一個位置
idx += 2
# 更新過去位置
x = new_x
print(ans)
```
### 第二子題-遞迴
先說一下這題的核心概念應該是考遞迴，不過因為ZJ上的測資會讓python遞迴沒辦法過
但是在APCS官方的測資中應該不會出現這種情況，所以ZJ沒過是正常的
(還是有解法，只是針對python了，我認為沒必要學那些，有興趣一樣私訊[我的IG](https://www.instagram.com/apcser_code_teacher/))
第二子題一樣有重點，我先幫各位整理出來了
1. 字串可以分為 $Tx$ 跟 $Ly...E$ 兩種
2. $Ly....E$ 中的字串要重複 $y$ 次
3. loop 字串中可以有另一個 loop 字串
4. loop 字串中至少有一個 $Tx$
5. T10L1L1L1L1L1L1T10EEEEEE => 0
先看第一個重點，字串 $S$ 雖然分為 $Tx$ 跟 $Ly...E$ 兩種，但是實際上也可以是
1. $Tx$ + 字串 $S$
2. $Ly$ + 字串 $S$ + $E$
所以我們程式碼可以改成判斷此格為 "T" 還是 "L" ，數字會在判斷時被用掉，只剩下 "E" 直接用else
假如遇到 $Tx$ 就跟第一子題一樣，和下一個數值相減就好
假如遇到 $Ly$ 就要開始找規律了，比如T10L2T15T13T17E這組測資展開就會變成
T10T15T13T17T15T13T17 => T10T15 + (T15T13T17) × 2 + (T17T15) × 1
可能你不太懂我為什麼要把字串分成後面那種形式，其實我是在**整理規律**
如果我們想要找到所有 $Ly...E$ 字串的快速計算方式，就是從規律開始
舉上面的例子來看，T10T15其實就是遇到 $Ly$ 前的**最後一個編號**跟 $Ly$ 字串的第一個編號組成
在 $Ly$ + 字串 $S_1$ + $E$ 的 $S_1$ 字串中，(T15T13T17) 重複了 $y$ 次，(T17T15) 重複了 $(y-1)$ 次
T10(T15T13T17)(T15T13T17) => 所以我們將(T15T13T17)的移動距離總和 × $y$
但是還有 T17T15 沒有考慮到，其實 (T17T15) 出現的次數就是 $S_1$ 字串首尾相連的次數
T10T15T13(T17T15)T13T17 => 而首尾相連的次數是 $y-1$ 次，所以 $(\mid\ 17-15\ \mid) × (y-1)$
最後只要注意，不論是在遇到 "T" 還是遇到 "L" 的時候，都有可能是沒有前一個編號的
所以還要做一個處理
```python=
start = -1 # 目前字串的第一個編號
end = -1 # 目前字串的最尾端編號
# now 為現在的編號
if end == -1 : start = now # 則 now 為字串的第一個編號
end = t # 遇到新編號都要更新最尾端編號
```
所以統整程式碼和想法後，我們的可以大致歸納出三個可能
1. 遇到 T ，如果有上一個編號就計算距離
2. 遇到 L ，按照規律處理 L 內字串
3. 遇到 E ，代表L結束，idx+1
遞迴的實現就是在多層 L 內發生的，最後我們來看程式碼
```python=
def rec():
global idx
sums = 0 # 目前字串總和
start = -1 # 目前字串的第一個編號
end = -1 # 目前字串的最尾端編號
while idx < len(s) :
if s[idx] == "T" :
now = int(s[idx+1:idx+3]) # 目前編號
if end == - 1 : start = now # 發現是第一個編號
else : sums += abs(now-end) # 計算和上一個編號距離
end = now # 更新最尾端編號
idx += 3 # 更新idx
elif s[idx] == "L" :
y = int(s[idx+1]) # 重複次數
idx += 2 # idx 要提前更新，準備遞迴
tsums, tstart, tend = rec()
# 若沒有start，更新start
if end == -1 : start = tstart
else : sums += abs(tstart-end)
end = tend # 更新最尾端編號
# 計算 L 內字串的值
sums += (tsums * y) + (abs(tend-tstart) * (y-1))
else : # s[idx] == "E"
idx += 1
return sums, start, end # 回傳值
return sums, start, end
# 輸入測資
s = input()
idx = 0
sums, start, end = rec()
print(sums)
```
總結:
最近第三題好像很常出現遞迴題目，我可能會考慮新增到PythonAPCS得遞迴篇當中
時間複雜度是 $O(n)$，如果你要用迴圈解也有，但是那已經是stack了，我之後再補上
最後補充，千萬不要展開方式解，最大長度10^5^，如果展開，**最長好像9^20000^**
### 第二子題-stack
所有的遞迴都能視作stack，把遞迴改成stack的關鍵也只有三個
1. 將遞迴回傳的變數改成放到stack
2. 迴圈重複次數也放入stack做為分界
3. 遇到 $E$ 時的操作要改變
第一點應該不難，只要現在的 $index$ 是當前子字串(層數)的第一個編號就要放入stack當中
第二點的概念是，假設我 $stack[-1]$ 是數字，那就代表這個子字串的第一個編號還沒出現
可以用 loop 做為一個分界去判斷，並在執行 $E$ 的時候將迴圈取出
最後只要用放入(各層第一個編號、總和、最後一個編號)跟 loop 的方式就可以**模擬遞迴**
```python=
# 輸入測資
s = input()
stack = [1] # 存放各層第一個編號，該層總和，最後一個編號
idx = 0 # 當前index
while idx < len(s) :
if s[idx] == "L" :
stack.append(int(s[idx+1])) # 紀錄迴圈次數
idx += 2 # 更新index
elif s[idx] == "T" :
now = int(s[idx+1:idx+3]) # 當前編號
idx += 3 # 更新index
if isinstance(stack[-1],int) : # 第一個數值
stack.append([now,0,now]) # 新增數值
else :
first, sums, end = stack[-1]
sums += abs(now-end)
stack[-1] = [first,sums,now] # 計算距離
else: # elif s[idx] == "E" :
idx += 1 # 更新index
first, sums, end = stack.pop() # 提出數值
times = stack.pop() # 提出迴圈次數
# 計算總和
sums = sums*times + abs(first-end)*(times-1)
if isinstance(stack[-1],int) : # 第一個數值
stack.append([first,sums,end]) # 新增數值
else :
# 計算距離
stack[-1][1] += sums + abs(first-stack[-1][2])
stack[-1][2] = end
print(stack[-1][1])
```
## 4. 開啟寶盒
[題目連結](https://zerojudge.tw/ShowProblem?problemid=k734)
已知有 $n$ 個寶盒編號 $0\sim(n-1)$ 以及 $m$ 種鑰匙編號 $0\sim(m-1)$，一開始你有 $k$ 種鑰匙
每一個寶盒要打開都需要同時擁有 $k$ 種鑰匙，第 $i$ 寶盒分別需要 $r_{i1},r_{i2},...,r_{ik}$ 種類的鑰匙
每個寶盒打開後都會得到 $k$ 種鑰匙，第 $i$ 個寶盒打開後分別會得到 $s_{i1},s_{i2},...,s_{ik}$ 種類的鑰匙
當拿到新的鑰匙之後可以繼續開啟新的寶盒
保證寶盒內的鑰匙不會重複，並且每種鑰匙可以開啟的寶盒數量不超過
請輸出最多可以開啟多少個寶盒
輸入說明 :
第一行輸入三個正整數 $n,m,k$ 代表有 $n$ 個寶盒，$m$ 種鑰匙以及每個寶盒需要的鑰匙數量
接下來輸入一行，第一個數字 $x$ 表示一開始有的鑰匙種類數量，後面有 $x$ 個數字代表這些鑰匙分別的種類
接下來有 $n$ 行，每一行有 $k$ 個數字，代表要開啟第 $i$ 個寶盒的第 $j$ 種鑰匙為 $r_{ij}$
最後有 $n$ 行，每一行有 $k$ 個數字，代表開啟第 $i$ 個寶盒後得到的第 $j$ 種鑰匙為 $s_{ij}$
輸出說明 :
輸出一個正整數，代表可以開啟的寶盒數量
解題思路 :
這題如果使用最暴力的方式就是每次拿到新的鑰匙就檢查能開的寶箱
不過這樣的演算法最多要 $n\ +\ (n-1)\ +\ ...\ +\ 1$ 次，時間複雜度就是 $O(n^2)$
很明顯在這種大測資的題目不能過關，所以我們使用拓樸排序(Topological sorting)
(如果不太懂拓樸排序的人可以先去學習)
先幫各位整理題目重點 :
* 一開始已經有鑰匙，但第一個數不是鑰匙
* 同個鑰匙可以開很多個寶箱
* 開啟寶箱後能拿到鑰匙(可能拿過)
把寶箱想像成一堂課，鑰匙是能否上課的條件，比如你要上線性代數的課程
你至少要有數學能力跟英文能力(讀原文書)
所以寶箱只要達到上述兩個條件就能打開，問題就是你要如何**同時判斷多個寶箱的條件**
其實可以**先找好所有需要數學能力**的課程，然後一次將這些課程所需的鑰匙數量-1
為了達到這種快速判斷的方式我們要做兩件事
1. 用一個List儲存寶箱"現在"所需的鑰匙數
2. 對於每個鑰匙記錄"所有"能開的寶箱
假設現在題目給你三個課程，線性代數、計算機概論、進階程式設計，這三個課程都**各需要兩個能力**
依序為(數學能力+英文能力)、(高階數學能力+英文能力)、(基礎程式設計能力+英文能力)
你現在只有數學能力的鑰匙，那你就什麼課都不能修，但是假設你再**拿到英文能力的鑰匙**
你就可以在第一輪拿到線性代數給的"高階數學能力"
第二輪就可以拿到計算機概論的"基礎計算機能力"(英文能力在第一輪就先被判斷完)
用這種方式就可以了，最後搭配BFS
```python=
from sys import stdin
# 輸入測資
n, m, k = map(int, stdin.readline().split())
# 持有的鑰匙(記得把第一個數字去除)
keys = list(map(int, stdin.readline().split()))[1:]
needs = [k] * n # 第index個寶箱還需要的鑰匙數量
gets = [] # 開啟第index個寶箱拿到的鑰匙
# 開啟第index個寶箱需要的鑰匙
opens = [[] for _ in range(n)]
have = [False] * m # 判斷是否擁有此鑰匙
# 先將拿到的鑰匙去除
for _ in keys : have[_] = True
for _ in range(n) :
# 輸入測資
for i in list(map(int, stdin.readline().split())) :
opens[i].append(_)
for _ in range(n) :
# 輸入測資
get = list(map(int, stdin.readline().split()))
gets.append(get)
ans = 0
while keys :
key = keys.pop() # 現在的鑰匙
# 跑過所有key能開的寶箱
for _ in opens[key] :
needs[_] -= 1 # 寶箱_所需鑰匙數-1
if needs[_] == 0 : # 寶箱開啟
ans += 1
for nk in gets[_] : # 跑過得到的鑰匙
if not have[nk] : # 如果nk鑰匙是沒拿過的
have[nk] = True
keys.append(nk) # 新增nk到持有的鑰匙
print(ans)
```
結論 :
時間複雜度是$O(kn+m)$
$m$ 是總共新獲得的鑰匙數量
$kn$ 是因為有 $n$ 個寶箱，如果每個都打開，就是 $n×k$ 次了
這次的APCS難度在中等，演算法不算是很難，算是圖論當中一定會講到的
反而考了兩次遞迴還滿特別的，我後續會加到pythonAPCS遞迴篇
Sign in with Wallet
Connect another wallet