寫完APCS題目後的碎碎念
本次題目基本上來說算是比較單純的
第一題是為迭代的基本題，以及如何在多個數字中找出最大最小值。
第二題是模擬題，考驗對於不同情境下的處理方式與邏輯，再輔以陣列進行記錄讀取，比起高難度的演算法更像是在考驗細不細心。
第三題考驗處理樹的能力，結合遞迴可以快速解決。
第四題可以使用二搜+BFS進行處理，但由於Python的限制怕TLE，所以是使用Dijkstra+BFS進行處理
ZeroJudge 題目
巴士站牌
題目簡述：
首先會輸入一個數字 n ，此 n 代表了站牌數量，接下來會有 n 行，每行2個整數代表了站牌座標，若有一人會依序經過這個n個站點，請計算相鄰兩站的曼哈頓距離(公式：| x1 – x2 | + | y1 – y2 | )。
最後輸出 最大 的曼哈頓距離以及 最小 的曼哈頓距離，中間需以空格做為間格。
假設 n 輸入5，分別為
2 8
2 1 -> |2-2| + |1-8| = 7
3 4 -> |3-2| + |4-1| = 4
5 8 -> |5-3| + |8-4| = 6
7 4 -> |7-5| + |4-8| = 6
有以上可以得知：最大值為7，最小值為4
有了以上概念後來思考一下簡單的解題步驟
1. 輸入：一個 n ，接下來利用for i in range(n) 來接 n 個兩個數字
2. 計算邏輯：必須先有第一對數字，接下來每一對數字皆跟上衣對數字進行曼哈頓距離的運算
3. 輸出：會需要最大值與最小值 -> 在開始迴圈時建立，並在計算過程中儲存
n = int(input()) #輸入n
maxNum,minNum = 0,401 #最小值必0，最大值必400
x1,y1 = map(int,input().split()) #第一對數字
for i in range(1,n):
x2,y2 = map(int,input().split()) #第二對數字
temp = abs(x2-x1)+abs(y2-y1) #曼哈頓距離公式
maxNum = max(maxNum,temp) #找最大值
minNum = min(minNum,temp) #找最小值
x1,y1 = x2,y2 #第二對數字變成第一對數字
print(maxNum,minNum) #輸出
以上為解題過程，若有任何意見歡迎留言。
運貨站
題面簡述：
共有n個貨物，其中貨物有五種不同的型狀，分別為A、B、C、D、E。
要將這些貨物放置在 R x C 的倉庫裡面，放置時會告知種類以及與天花板的距離，接著要推到倉庫的最左端
放置並且與天花板的距離必須維持一致。若不能完整放置至倉庫則丟棄。
最後要輸出倉庫剩下多少空位以及被遺棄的貨物數量。
這題的重點其實在於子題的分數配置，前20%為只有 B 的狀況，40%為有 A、B、C 的狀況，最後40%才是全部都有的狀況。
此時稍微思考一下會有些發現。
當只有B的時候基本上來說會把所有空格填滿(除了超出範圍的)，所以不必要去計算最左邊的倉庫剩下那些空格。
這時候開始出現空格了，每當降落時就必須要計算所會造成的空格，但至少還是同一個平面還好處理。
當有D與E時就會比較麻煩，必須在墜落後去判斷到底是往右推移3格2格還是1格。
有了以上概念之後來稍微思考一下解題步驟：
1. 輸入1：三個數字 R C N，R 跟 C 就是寬跟高，N是貨物數量。
2. 輸入2：for i in range(N)，用來輸入貨物種類與頂部的距離。
3. 邏輯1：紀錄，這題的重點在於如何記錄，如果對這比較不擅長的或許可以使用matrix紀錄，但個人只用一條array紀錄，專門記錄與倉庫左端的距離。
4. 邏輯2：統計空白，看要用加法還是減法，減法會相對而言簡單一些。
5. 輸出：以上都有好好做的話基本上沒什麼困難的
個人在考試時會先完成第一子題與第二子題拿這60分即可，第三子題等後面題目完成再回來做。
block = { #寬, 高, 格子數
"A": (1, 4, 4),
"B": (3, 1, 3),
"C": (2, 2, 4),
"D": (3, 2, 4),
"E": (2, 3, 5)
}
r, c, n = map(int, input().split())
total_block = r*c #總空格數
out = 0 #要被丟掉的貨物
row = [0 for i in range(r)] #計算距離
for i in range(n):
block_type, top = input().split() #貨物種類、天花板距離
top = int(top)
bottom = top + block[block_type][1]
clone_row = row[:][top:bottom] #這邊要deepclone否則會改到原資料
for index in range(block[block_type][1]): #D跟E比較麻煩要拉出來算
if block_type == 'D' and index == 0:
clone_row[index] += 1
elif block_type == 'E' and index == 0:
clone_row[index] += 1
else:
clone_row[index] += block[block_type][0]
max_R = max(clone_row)
if max_R > c: #判斷該貨物是否要被丟棄
out += 1
else:
row[top:bottom] = [max_R for j in range(block[block_type][1])]
#確定最終高度再一起改回到原row
total_block -= block[block_type][2]
print(total_block, out)
以上為解題過程，若有任何意見歡迎留言。
石窟探險
題目簡述：
有 n 個石窟形成樹狀結構，每個石窟都會有一個 val ，若此 val 為偶數則有 2 個分支，奇數則為 3 個分支。取所有相鄰的兩個石窟的 val 進行減法取絕對值的總和。
重點是要如何知道此兩數是相鄰的，題目所給予的數列是已經透過 preorder traversal過的結果。所以只要接著他的結果做 dfs 即可。
有了以上概念之後來稍微思考一下解題步驟：
1. 輸入：數列切割轉整數
2. 邏輯：遞迴+判斷 val 奇偶數決定接下來要走的節點
若輸入的數字為 2 4 0 5 0 0 0 6 0 0
numList = list(map(int,input().split()))
ans,index = 0,1
#因為index必須往下讀取numList的東西
#所以global比較方便，ans亦同(或用list也可以)
def run(num):
global index,ans
for i in range(num%2+2):#偶數節點跑兩個，奇數跑三個
val = numList[index]
index+=1
if val == 0:#遇到空節點
continue
ans+=abs(num-val)#計算相鄰
run(val)
run(numList[0])
print(ans)
以上為解題過程，若有任何意見歡迎留言。
蓋步道
題目簡述：
給一個 n x n 的方形區域，每一個都有整數 h 代表海拔高度。想辦法從左上角走到右下角，每一步的高低落差越小越好。最後要求出最小的最大高度差，以及用此方案所走出來的路徑長。
這題題目其實滿好理解的，重點是後續要如何處理。
有了以上概念之後來稍微思考一下解題步驟：
1. 輸入1：一數字 n 代表此方型區域的邊長。
2. 輸入2：多個整數，整數與整數間有空格，代表每一格的高度。
3. 邏輯1：首先要找出最小的最大高度差 -> 二搜或Dijkstra
4. 邏輯2：利用此高度差跑BFS確認路徑
5. 輸出：就，輸出。
from collections import deque
import heapq
n = int(input())
matrix = []#存高度
movement = ((1,0),(0,1),(-1,0),(0,-1)) #跑位移用
for i in range(n):
matrix.append(list(map(int,input().split())))
table = [[0 for i in range(n)] for i in range(n)] #紀錄路徑
cashs = [[10**6 for i in range(n)] for i in range(n)] #紀錄高低差
heap = [(0,0,0)] #用heap存座標與高低差
while heap:
x,y,cash = heapq.heappop(heap)
for i in movement: #座標
newX,newY = x + i[0],y + i[1]
if n>newX>=0 and n>newY>=0:
nextCash = max(cash,abs(matrix[newX][newY] - matrix[x][y]))
if cashs[newX][newY] > nextCash:
cashs[newX][newY] = nextCash
heapq.heappush(heap,(newX,newY,nextCash)) #高低差紀錄
print(cashs[-1][-1])
queue = deque()
queue.append((0,0,1))#座標、路徑
while queue:
x,y,temp = queue.popleft()
if table[x][y]:#走過不走
continue
table[x][y] = temp
for i in movement:
newX,newY = x + i[0],y + i[1]
if n>newX>=0 and n>newY>=0 and abs(matrix[newX][newY] - matrix[x][y]) <= cashs[-1][-1]:
queue.append((newX,newY,temp+1))
print(table[-1][-1]-1)#利用最小的最大高度差必可以走完全程
以上為解題過程，若有任何意見歡迎留言。
