# APCS 2024.10實作題題解 --- C++與Python
在這份筆記中，我們說明APCS 2024年10月實作題考試的題目解說。這些題目是根據ZeroJudge上的版本，與真實考試的版本題意應該是一樣的，但題目敘述、測資與環境並不一定相同。
每一題的題解都包含題意分析、演算法、C/C++範例程式與Python範例程式。其中後兩個單元是獨立的，也就是必要的說明會在兩個單元重複出現，為了方便有些人只看其中一種語言。
## 第一題 裝飲料 (ZeroJudge o711)
### 題意分析
[(題目連結)1.裝飲料](https://zerojudge.tw/ShowProblem?problemid=o711)
有一個水杯，上下兩層是底面積都是正方形，但邊長不同。逐次加入若干體積的水，問哪一次水面高度增加的最多，假設水杯若滿，則高度不再增加。輸出水面高度最大一次的增幅。
### 演算法構思與程式流程
假設下層的邊長與高度是$w_1$與$h_1$，而上層的邊長與高度是$w_2$與$h_2$。
這個問題可以先分兩段來思考。
* 給定水的體積$Q$，計算水面的高度。這就是個簡單的數學題(大概是國中或國小的程度吧？)， 先求出下層與上層各自的體積(容積)$V_1$與$V_2$。分成三個情況
* 水量不超過下層的體積($Q\leq V_1$)。高度是 $Q/(w_1^2)$。
* 水量超過下層的體積，但未超過總體積($V_1<Q\leq V_1+V_2$)。高度是$h_1+(Q-V_1)/(w_2^2)$。
* 水量超過$V_1+V_2$。高度是$h_1+h_2$。
* 假設已知每次加完水會的高度依序是$(0,p_1,p_2,\ldots p_n)$，求一次的最大增加高度。初始的0是一開始杯子是空的，這計算最大增量就是找$\max\{p_i-p_{i-1}\}$，我們可以一路掃過去，記錄著前一個$p_{i-1}$的值，每次計算差值後，取目前看到的最大差。
第一子題是只有一次加水，也就是只要會上述的第一項即可。完全解則需要一個迴圈。
### C/C++範例程式
先看第一子題的解，只要將前述的三個情形用if來判斷區分即可。
```cpp=
// subtask 1, n=1
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, w1,w2,h1,h2,water,height;
cin >>n;
cin >>w1>>w2>>h1>>h2;
cin >> water;
int low = w1*w1*h1; // vol of the lower
int full = low+w2*w2*h2; // total vol
// find curr height
if (water<=low) { // <= h1
height = water/(w1*w1);
} else if (water<=full) { // between h1 and h2
height = h1+(water-low)/(w2*w2);
} else { // full case
height = h1+h2;
}
cout<<height<<endl;
return 0;
}
```
接著是完全解的寫法。除了輸入的尺寸參數外，我們使用以下變數：
* low: 下層的體積
* full: 上下層合併的體積。
* total: 目前的總水量。
* prev: 前一次的水面高度，初值為0。
* curr: 本次加水後的高度。
* imax: 目前看到的最大增量。
程式就直接依照上述定義好的變數來做就可以了，記得在下一回合開始之前，要用curr更新prev的值。
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,i,w1,w2,h1,h2,total=0,prev=0,curr=0,imax=0,water;
scanf("%d",&n);
scanf("%d%d%d%d",&w1,&w2,&h1,&h2);
int low = w1*w1*h1; // vol of the lower
int full = low+w2*w2*h2; // total vol
for (i=0;i<n;i++) {
scanf("%d",&water);
total += water; // current total water
// find curr height
if (total<=low) { // <= h1
curr = total/(w1*w1);
} else if (total<=full) { // between h1 and h2
curr = h1+(total-low)/(w2*w2);
} else { // full case
curr = h1+h2;
}
// check if increment > imax
if (curr-prev > imax) imax = curr-prev;
prev = curr;
}
printf("%d\n",imax);
return 0;
}
```
### Python範例程式
先看第一子題的解，只要將流程中所說的三個情形用if來判斷區分即可。使用Python者需要對list有基本認識以方便處理輸入，以下面的程式前兩行為例，第一行是一行數入一個整數，第二行是一行輸入若干個以空白間隔的整數，這是常用的方法，必須一記。
```python=
n = int(input())
w1,w2,h1,h2 = [int(x) for x in input().split()]
water = int(input())
if water <= w1*w1*h1: # <=h1
height = water//(w1*w1)
elif water <= w1*w1*h1+w2*w2*h2: #between h1 and h1+h2
height = h1+(water-w1*w1*h1)//(w2*w2)
else: # full
height = h1+h2
print(height)
```
接著是完全解的寫法。除了輸入的尺寸參數外，我們使用以下變數：
* lower: 下層的體積
* full: 上下層合併的體積。
* total: 目前的總水量。
* prev: 前一次的水面高度，初值為0。
* curr: 本次加水後的高度。
* imax: 目前看到的最大增量。
程式就直接依照上述定義好的變數來做就可以了，記得在下一回合開始之前，要用curr更新prev的值。
```python=
n = int(input())
w1,w2,h1,h2 = [int(x) for x in input().split()]
lower = w1*w1*h1
full = lower+w2*w2*h2
total = 0 # current total water
prev = 0 # previous height
imax = 0 # max height
for water in [int(x) for x in input().split()]:
total += water
if total <= lower: # lower layer
curr = total//(w1*w1) # current height
elif total <= full:
curr = (total-lower)//(w2*w2)+h1 # second layer
else:
curr = h1+h2
imax = max(imax,curr-prev) # inc = curr-prev
prev = curr
#
print(imax)
```
## 第二題 蒐集寶石 (ZeroJudge o712)
### 題意分析
[(題目連結) 2.蒐集寶石](https://zerojudge.tw/ShowProblem?problemid=o712)
模擬在一個$m\times n$的方格圖中行走，碰到寶石就撿起一顆，碰到牆壁或是界外就右轉，同時要記錄一個分數，每次走到有寶石的格子，得分就增加該格目前寶石數量，如果目前總得分是$k$的倍數，要右轉。走到沒有寶石的格子就結束。
### 演算法構思與程式流程
這就是個模擬的題目，只要定義好變數記錄狀態，依照題意來寫就可以。不過方格圖的走訪有些小技巧，如果沒有經驗可能寫得又臭又長。
依照題目的定義，我們以橫列與直行來定義位置，$(r,c)$代表第$r$個橫列的第$c$個直行的位置，列與行的編號皆從0開始。我們紀錄以下的變數
* g[r][c]：在格子$(r,c)$目前寶石的數量，以-1表示牆壁。
* d：目前的方向。以0,1,2,3分別當做東南西北，這樣有個好處，右轉就是+1再除以4取餘數，如果在其他題目，也可以用+3來當作左轉，+2就是後轉(都是除4的餘數)。
* cnt：目前蒐集到寶石的數量
* score：目前的分數
### C/C++範例程式
第一子題是一維陣列，流程可以更簡化，以下直接說明完全解。這題是簡單的題目，C與C++差異不大，以下提供C的寫法。
第7 ~ 12行是輸入的部分，在一開始我們可以將四周圍滿一圈-1，這樣後面就不必檢查出界，所以第8行會將m與n的值加2，當然要記得開始的座標要改成$(r+1,c+1)$。
第16行開始的while迴圈開始模擬行走，因為題目保證開始的位置不是牆壁(-1)，所以結束的條件是走到的位置不是0。第21行是判斷如果得分是k的倍數就右轉。無論得分有沒有讓我們右轉，接下來第22 ~ 33行我們用一個迴圈轉到前方不是牆壁也不是界外為止，然後往前走進入下一回合。
當while迴圈結束後，印出答案即可。
```c=
#include <stdio.h>
#include <stdlib.h>
int main() {
int m,n,r,c,k,i,j;
int g[102][102];
scanf("%d%d%d%d%d",&m,&n,&k,&r,&c);
m += 2; n += 2; r++; c++; // surrounding -1 as wall
for (i=0;i<m;i++) for (j=0;j<n;j++) {
if (i==0 || i==m-1 || j==0 || j==n-1) g[i][j]=-1;
else scanf("%d",&g[i][j]);
}
int d=0, // current dir
score=0, // current score
cnt = 0; // num of collected
while (g[r][c]>0) { // until 0
cnt++;
score += g[r][c]; // update score
g[r][c]--;
score %= k; // check if score is multiple of k
if (score==0) d=(d+1)%4; // turn right
for (j=0;j<4;j++) { // turn right until not wall
int nr=r,nc=c; // next row, next column
if (d==0) nc++; // east
else if (d==1) nr++; // south
else if (d==2) nc--; // west
else nr--; // north
if (g[nr][nc]>=0) { // not wall
r=nr; c = nc;
break;
}
d = (d+1)%4; // next dir
}
}
printf("%d\n",cnt);
return 0;
}
```
### Python範例程式
第一子題是一維陣列，流程可以更簡化，以下直接說明完全解。第1 ~ 5行是輸入，我們把方格圖的四周圍一圈-1，可以簡化後面不需要判斷出界，因為Python list的[-1]是最後一個，所以我們只要在每一列的後方與最後一列加上-1就可以了(第4,5行)。
第9,10行是定義對於每一個方向(d=0,1,2,3)，列與行的變化量，例如在d=0(東方)時，往前一步就是dr=0,dc=1。這是個在方格圖中走訪的常用技巧。
第11行的while迴圈開始走訪，迴圈不變性是g[r][c]是目前所在位置，停止條件是g[r][c]不是0。第12 ~ 14是調整變數的內容，第15行判斷分數是否為k的倍數，若是則右轉。第16行的迴圈會持續右轉直到前方不是牆壁，注意這樣寫while True是因為進入迴圈先不轉，到迴圈尾巴才右轉。
離開while迴圈後，印出答案即可。
```python=
m,n,k,r,c = [int(x) for x in input().split()]
g = []
for i in range(m):
g.append([int(x) for x in input().split()]+[-1])
g.append([-1]*n) # surrounding -1
d = 0 # current direction
score = 0 # current score
cnt = 0 # number of collected stone
dr = (0,1,0,-1) # east,south,west,north
dc = (1,0,-1,0) # row and col difference
while g[r][c]: # until 0
cnt += 1 # num of collected
score += g[r][c] # update score
g[r][c] -= 1 # update g
if score%k==0: d = (d+1)%4 # multiple, turn right
while True: # until not wall
nr = r+dr[d]; nc = c+dc[d] # forward step
if g[nr][nc] >= 0:
r,c = nr,nc
break
d = (d+1)%4
# while next direction
#
print(cnt)
```
## 第三題 連鎖反應 (ZeroJudge o713)
### 題意分析
[(題目連結) 3. 連鎖反應](https://zerojudge.tw/ShowProblem?problemid=o713)
有一個方格圖，裡面有一個指定的起始點(-2)，其他點如果是-1就是牆壁，否則都是地雷，地雷有一個非負整數表示爆炸的半徑(傳播距離)，地雷被引爆時，在傳播距離以內的其他地雷會被引爆，可以形成連鎖反應。傳播距離的計算是往上下左右一格算一步，但不能傳入牆壁。
題目要計算的是：找出起爆點的最小爆炸半徑，使得至少有q個地雷被引爆。此處有些地雷的爆炸半徑是0，也就是它被引爆時並不會影響其他地雷，但是它也要被計算在被引爆的地雷數量中。
有三個子題，第一子題沒有牆壁，也就是說兩點的距離就是列差與行差的和，地雷可以傳到的點可以很簡單的來判斷。第二與第三子題有牆壁，距離的計算方式要使用BFS來做。此外測資的大小也是隨子題增加，所以對效率的要求也是重要的要求。
### 演算法構思與程式流程
第一子題雖然比較簡單，但主要的一些觀念與程式的主要結構是一樣的，我們可以用第一子題來講解主要流程，第二三子題只要更換計算距離的程序就好。
先看看地雷爆炸的連鎖反應是怎麼回事。
地雷A爆炸時，在距離範圍內如果有BCD，則BCD也會爆炸，BCD可能進一步引爆其他的地雷，如此連續引爆下去直到沒有地雷被引爆。這其實是個遞迴的過程，其中有個重點就是地雷不會重複被引爆，否則會形成無窮遞迴。所以它也就是個圖形的走訪，可以用DFS來做，或者用個stack寫非遞迴版本。流程可以規劃如下：
```clike
// 連鎖反應的DFS
// 陣列done[r][c]=1表示(r,c)位置已經引爆過
int dfs(r,c) // 回傳新爆炸的數量
if (r,c) is outside or done[r][c]==1 then
return 0;
cnt = 1;
done[r][c] = 1;
for each point (x,y) in my range do
cnt += dfs(x,y);
return cnt;
// end of dfs
```
**見山是山**
要計算最小起爆半徑，我們可以逐步嘗試0,1,2,...，直到爆炸數量滿足需求。
**見山不是山**
可以做得更好嗎？
爆炸數量顯然與起爆半徑的單調上升函數，可以外面套一層二分搜減少搜尋次數。
**見山還是山**
如果先找好所有點與起爆點的距離，依照距離由近而遠引爆並進行連鎖反應，記錄好done的值，不重複進行連鎖反應，那麼我們不需要二分搜，第一個滿足總爆炸數量的點與起始點的距離就是最小起爆半徑。
總結我們的程序
* 初始化done
* 計算所有點與起點的距離，並將它們依照距離由小而大排入queue
* 歷遍queue，對於每個點(r,c)距離起點d：
* 用dfs(r,c)計算引爆所造成連鎖反應的新引爆數量
* 如果總爆炸數量滿足需求，則答案為d，結束；
時間複雜度跟如何計算所有點距離以及如何計算在一個地雷範圍內的點有關，計算所有點的距離是陣列大小$O(mn)$；一個爆炸半徑$r$的地雷可以引爆的範圍是$O(2r^2)$，因為不會重複引爆，所以這部分是$O(2kr^2)$，$k$是半徑非零的地雷數，總時間複雜度是$O(mn+2kr^2)$，本題中$m,n\leq 500$，$r\leq 30$，$k\leq=1500$。不是很大，即使外層用二分搜的較差版本應該也可以通過。
第二三子題需要用BFS在有牆壁的方格圖中走訪，因為要做多次的BFS搜尋，因此應該單獨寫下BFS的副程式，這是個常用的標準程序，但有幾個小細節要注意：
* 這裡的BFS有步數的限制，走到限制就停下來
* 要回傳走訪的點，所以不要用程式語言中的queue，用list或陣列就好。
* BFS本身有個需要紀錄是否走過的動作，這個與上面連鎖反應的done不同，這裡有點小麻煩。因為每個地雷的座標不一樣，我們也不能每次都使用一個$m\times n$的大陣列來做，因為初始大陣列太耗時間。有幾個簡單的解決方法，使用其中任何一個都可以。
* 使用一個global的大陣列，每次只清理與使用自己的可能範圍就好。
* 用一個$(2r+1)\times (2r+1)$的小陣列，然後用座標平移的方式處理，這裡$r$是爆炸半徑。
* 用字典的方式來記錄。
以下是BFS的流程
```clike
// 計算一點能到達的BFS，起點(r,c)步數限制step
// 陣列d[r][c]=-1表示沒走過，走過的存距離>=0
// 將牆壁的d值設為非0，就不會走入牆壁
dfs(r,c,step) // 回傳走訪個的點與距離
初始化d陣列;
準備一個陣列queue存放待走的點,head指著目前的點
head = 0;
d[r][c] = 0;
while head < queue的長度 do
目前座標 (r,c) = queue[head]; head += 1;
if d[r][c]==step then break; //結束
for (r,c)的四個鄰居 do
if 在界內且d值==-1 then
將鄰居放入queue且設其d值為d[r][c]+1
end for
end while
回傳queue與d值;
end of BFS
```
整體來說，這個題目的思考並不是算太過困難，但很吃實作能力，而且APCS沒有online judge，必需對BFS/DFS了解並且有足夠的熟練度，才能在考試的有限時間內寫得出能通過的程式。
### C/C++範例程式
先看第一子題的寫法，比較容易了解此題的架構。
第五行的g是地圖，另外我們把標記是炸過的done放在global。第6行開始是進行連鎖反應的dfs。進入時先檢查是否界內以及是否已經引爆，是的話直接回傳0。
否則我們引爆此地雷，cnt=1, done[r][c]=1，然後要對範圍內的點進行遞迴呼叫，第一子題就直接檢查可能範圍內的所有座標就可以，這裡有更快的寫法，但並不需要。所謂可能範圍就是列差值與行差值都在半徑以內。
再看主程式的部分。第21 ~ 28行是輸入，這題須要自己找起始點，我們在第24行檢查，找到了用r0,c0紀錄。第28行先初始化done，然後要找所有點與起始點的距離，這裡我們直接歷遍所有的點，依照座標計算距離然後放入queue，此處用vector of vector來做，把距離放在最前面，這樣用排序就可以達到我們的目的，不需要使用更複雜的方法。
第35行開始的迴圈，我們依照距離由近而遠歷遍queue的所有點，呼叫dfs計算新引爆的地雷，如果數量達到，就結束並輸出答案。
```cpp=
// subtask 1
#include <bits/stdc++.h>
using namespace std;
#define N 500
int g[N][N],m,n,done[N][N];
int dfs(int r,int c) {
if (r<0 || r>=m || c<0 || c>=n || done[r][c])
return 0;
done[r][c] = 1;
int cnt=1,i,j,x=g[r][c];
for (i=r-x; i<=r+x; i++) {
for (j=c-x; j <=c+x; j++) {
if (abs(i-r)+abs(j-c)<=x) cnt += dfs(i,j);
}
}
return cnt;
}
int main() {
int i,j,req,r0=-1,c0,k=0,out=0;
scanf("%d%d%d",&m,&n,&req);
for (i=0;i<m;i++) for (j=0;j<n;j++) {
scanf("%d",&g[i][j]);
if (g[i][j]==-2) {
r0=i; c0=j;
}
}
for (i=0;i<m;i++) for (j=0;j<n;j++) done[i][j]=0;
vector<vector<int>> que;
for (i=0;i<m;i++) for (j=0;j<n;j++) {
que.push_back({abs(i-r0)+abs(j-c0), i, j});
}
sort(que.begin(),que.end());
int radius, cnt = 0;
for (auto p: que) {
radius=p[0],i=p[1],j=p[2];
cnt += dfs(i,j);
if (cnt>=req) {
printf("%d\n",radius);
break;
}
}
return 0;
}
```
完全解的差異在於距離的計算要使用BFS，先看第8行開始的BFS。這裡我們採用一個大的工作陣列dis來處理每次BFS計算距離時的需要，回傳queue的部分則用傳reference的方式來做，這裡當然也有其他的方法，例如用global變數也可以做。
dr,dc是要拜訪4個鄰居時候的列差值與行差值，是方格圖的常用手法，第12 ~ 16行初始dis陣列，只清理我們能夠走得到的範圍就可以，其中牆壁的位置放0，後面就不會走進去牆壁裡面。接著就照前面的流程，這裡的que是個vector<pair<int,int>>用來放座標，所以列座標在first而行座標在second。第24行的迴圈檢查4個鄰居，他們的座標(nr,nc)可以用dr,dc簡單得到。
接著看DFS，在第35行開始，這與前面第一子題的架構差不多，但我們這裡確定呼叫進來的不會是爆過的，而且我們用g[r][c]=-2表示爆炸過，省略用另外一個陣列done。第38行如果範圍是0就不做遞迴，否則第39行準備一個q2，第40行呼叫BFS，然後我們會得到可以走得到的點在q2中，然後對它們一一遞迴呼叫，此處的順序是不重要的，順便一提。
主程式的部份，第57 ~ 59行先做一次起始點的BFS，距離限制給$m\times n$相當於無限大，得到拜訪點的順序會存在que中，並且也把距離保存在d中，此處的距離是要用的而且順序是重要的。後面的部分與第一子題相同，依照que的順序一一呼叫dfs。
```cpp=
// dfs+bfs
#include <bits/stdc++.h>
using namespace std;
#define N 500
int g[N][N],m,n,dis[N][N],d[N][N];
// distance<=step will be in que
void bfs(int r,int c,int step,vector<pair<int,int>> &que) {
// dr,dc = row and col difference, east,south,west,north
int head = 0,i,j,dr[4]={0,1,0,-1},dc[4]={1,0,-1,0};
// -1 = unvisited; wall=0 as visited
for (i=max(r-step,0);i<=min(r+step,m-1);i++) {
for (j=max(c-step,0);j<=min(c+step,n-1);j++) {
dis[i][j] = (g[i][j]==-1)? 0: -1;
}
}
que.push_back({r,c});
dis[r][c] = 0;
while (head < que.size()) {
r = que[head].first;
c = que[head].second;
head++;
if (dis[r][c]>=step) continue;
for (i=0;i<4;i++) {
int nr = r+dr[i],nc=c+dc[i];
if (nr>=0 && nr<m && nc>=0 && nc<n && dis[nr][nc]==-1) {
dis[nr][nc] = dis[r][c]+1;
que.push_back({nr,nc});
}
}
}
return;
}
// explore all reachable
int dfs(int r,int c) {
int cnt=1,x=g[r][c];
g[r][c]=-2; // -2 as visited
if (x==0) return cnt;
vector<pair<int,int>> q2;
bfs(r,c,x,q2);
for (auto v:q2) { // check each of my reachable
if (g[v.first][v.second]!=-2) { // not visited
cnt += dfs(v.first,v.second);
}
}
return cnt;
}
int main() {
int i,j,r,c,r0=-1,c0=-1,x,req;
scanf("%d%d%d",&m,&n,&req);
for (i=0;i<m;i++) for (j=0;j<n;j++) {
scanf("%d",&g[i][j]);
if (g[i][j]==-2) { // starting point
r0=i; c0=j;
}
}
vector<pair<int,int>> que; // visit all from starting point
bfs(r0,c0,m*n,que);
for (i=0;i<m;i++) for (j=0;j<n;j++) d[i][j]=dis[i][j]; // save distances
int total=1,radius=-1, cur_rad=0; // req>1, radius!=0
for (auto p: que) { // iter each point near to far
r = p.first; c = p.second; // the next point
if (g[r][c]==-2) continue; // visited
total += dfs(r,c);
if (total>=req) { // ans found
radius = d[r][c];
break;
}
}
printf("%d\n",radius);
return 0;
}
```
### Python範例程式
以下介紹Python的範例。
先看第一子題的寫法，比較容易了解此題的架構。
第1 ~ 7行是輸入，第8行是要標記是炸過的done，這題須要自己找起始點，在第6 ~ 7行找，找到了就用r0,c0紀錄。
第10行開始是進行連鎖反應的dfs。進入時先檢查是否界內以及是否已經引爆，是的話直接回傳0。否則我們引爆此地雷，cnt=1, done[r][c]=1，然後要對範圍內的點進行遞迴呼叫，第一子題就直接檢查範圍內的所有座標就可以，這裡有更快的寫法，但並不需要。所謂可能範圍就是列差值與行差值都在半徑以內。
再回到主程式的部分。第21 ~ 22行是找所有點與起始點的距離，這裡我們直接歷遍所有的點，依照座標計算距離然後放入que，每個點存距離與座標共3個整數，把距離放在最前面，這樣用排序就可以達到我們的目的，不需要使用更複雜的方法。
第25行開始的迴圈，我們依照距離由近而遠歷遍que的所有點，呼叫dfs計算新引爆的地雷，如果數量達到，就結束並輸出答案。
```python=
# subtask 1, dfs iteratively deeping
m,n,req = [int(x) for x in input().split()]
g = []
for i in range(m):
g.append([int(x) for x in input().split()])
if -2 in g[-1]:
r0,c0 = i,g[-1].index(-2)
done = [[0]*n for i in range(m)] # if already exploded
# dfs return number of new exploded
def dfs(r,c,done):
if r<0 or r>=m or c<0 or c>=n or done[r][c]:
return 0 # outside or already exploded
done[r][c] = 1 # explode
cnt=1; x=g[r][c]
for i in range(r-x, r+x+1):
for j in range(c-x, c+x+1):
if abs(i-r)+abs(j-c)<=x: cnt += dfs(i,j,done)
#
return cnt
# que of all points sorted by distance
que = [(abs(i-r0)+abs(j-c0), i, j) \
for i in range(m) for j in range(n)]
que.sort()
cnt = 0
for radius,i,j in que:
cnt += dfs(i,j,done)
if cnt>=req:
print(radius)
break
#
```
完全解的差異在於距離的計算要使用BFS，先看第8行開始的BFS。這裡我們採用一個大的工作陣列tem(在bfs內稱為d)來處理每次BFS計算距離時的需要。
第11 ~ 13行初始d陣列，只清理我們能夠走得到的範圍就可以，其中牆壁的位置放0，後面就不會走進去牆壁裡面。接著就照前面的流程，這裡的que中放的是座標tuple。第19行的迴圈檢查4個鄰居的座標(r,c)，是方格圖的常用手法，如果座標在界內且未走過，就設定距離並加入que的尾端。
接著看主程式。第26行開始計算程序，這與前面第一子題的架構差不多，但我們不寫遞迴的DFS，因為Python的遞迴深度與記憶體限制比較嚴，我們採用非遞迴的stack方式來做。
第26 ~ 27行先做一次起始點的BFS，距離限制給$m\times n$相當於無限大，得到拜訪點的順序回傳到reach中，此處的距離是後面要用的，所以用另外一個dist傳過去以便保存。後面部分與第一子題相同，依照reach的順序一一檢查連鎖反應，也就是DFS，非遞迴的DFS其實很簡單，第39行準備一個stack，一開始把此次引爆的第一點放入，每次從stack取出最後一點，呼叫bfs找到它可以引爆的點，將它們放入stack中，一直跑到stack空為止。我們這裡用g[r][c]=-2表示爆炸過，並且只有半徑>0的才做，以便減少沒用的bfs呼叫浪費時間。
```python=
m,n,req = [int(x) for x in input().split()]
g = []
for i in range(m):
g.append([int(x) for x in input().split()])
if -2 in g[-1]:
r0,c0 = i,g[-1].index(-2)
tem = [[-1]*n for i in range(m)]
# BFS from (r,c) with distance<=step,
def bfs(r,c,step,d):
# d=-1 as unvisited, make d[wall]=0 as visited
for i in range(max(r-step,0),min(r+step+1,m)): #
for j in range(max(c-step,0),min(c+step+1,n)):
d[i][j] = -1 if g[i][j]!=-1 else 0
que = [(r,c)]; head = 0
d[r][c] = 0
while head < len(que):
i,j = que[head]; head += 1
if d[i][j]==step: break
for r,c in ((i,j+1),(i+1,j),(i,j-1),(i-1,j)):
if 0<=r<m and 0<=c<n and d[r][c]==-1:
d[r][c] = d[i][j]+1
que.append((r,c))
#
return que
# end bfs
dist = [[0]*n for i in range(m)] # save distance
reach = bfs(r0,c0,m*n,dist) # visit all from starting
total = 1
radius =0 # assume req>1
for r,c in reach:
if g[r][c]==-2: continue # counted
radius = dist[r][c] # current radius
total += 1 # number of visited
if total>=req: break
x = g[r][c]
g[r][c] = -2 # mark as counted
# count all reachable, similar as DFS
if x==0: continue
stk = [(r,c,x)] # stack
while stk:
r,c,x = stk.pop()
que = bfs(r,c,x,tem)
for r,c in que:
x = g[r][c]
g[r][c] = -2
if x>=0: total += 1
if x>0: stk.append((r,c,x))
#
if total>=req: break
#
if total<req: print(-1)
else: print(radius)
```
## 第四題 搭到終點 (ZeroJudge o714)
### 題意分析
[(題目連結) 4.搭到終點](https://zerojudge.tw/ShowProblem?problemid=o714)
有$n$班車，每班行駛在某個連續的區間。要從0搭到$m$，每搭上一班車，就要搭到該班車的終點，不可中途下車，到該班車終點下車後，再轉乘其他經過的車，任何經過的車都可以搭，但已到站的車不可搭(也就是不能上車沒有前進就下車)。請問有幾種搭車到達最後一站$m$的方法數。輸出方法數除以P的餘數，P是輸入的正整數。
$n\leq 2\times 10^5$，$m\leq 10^9$。
第一子題n,m很小，第二子題$m\leq 10^5$。
### 演算法構思與程式流程
這題的題意明顯，如果具備有DP(動態規劃)知識者，很容易知道要怎麼做。令dp(i)是搭到i的方法數，對於一個行駛區間為$[s,t]$的列車，它貢獻給$t$點的方法數就是
$\sum_{i=s}^{t-1} dp(i)$這個區間和，當然這裡假設在他之前所有點的到達數都已經算好了。
所以，我們將到達點由小到大的順序，依照這個計算式來計算方法數就可以算出最後答案。
如果按照定義來天真的直接實作，時間複雜度是所有區間的長度總和，也就是$O(mn)$，這顯然太大，只能過第一子題。
如何加速呢？
要算區間和，就用前綴和。因為此處每個點的DP值算好了就不會再變動，所以用前綴和就可以。不過有幾點要注意：
* 首先當然先用終點(也就是右端)排序。
* 因為DP值是一路逐步計算出來的，所以需要必須一面產生一面計算前綴和。對於每一班列車，相同終點是不加入計算的，所以對於相同終點的車要小心處理。
* 第3子題的座標範圍大，需要先做離散化或者用二分搜找起點的範圍。
* 答案(因為可能太大)最後要對輸入的參數P取餘數。取餘數要在計算過程中取，不能到算完之後再取。這裡有個數學性質，「兩數相加取餘數」等於「各自先取餘數後相加，再取餘數」。這個道理應該很淺顯，例如
1232362153716261737612317653
與
2834763276826482738271
相加後除以100的餘數是24。不過，加法與乘法都沒問題，可以先取餘數後再運算，運算完再取一次餘數。但減法要注意，因為每一種語言對於負整數取餘數的定義不同，例如C與Python就不一樣，所以相減取餘數時，習慣上最好採用
(a-b+mod)%mod
的方式(假設a,b都在範圍內)。
我自己做題目常常會踩到一個雷，就是忘記取餘數，但我看這題把P放在輸入，就是讓忘記取餘數的人在範例中就會發現，競賽題中的P常常訂死在題目中$P=10^9+7$，那麼在小測資時就不會發現，順帶一提。
這裡我們不用離散化，而用二分搜的方法。演算法如下：
```
輸入並組成每一個列車的區間
將區間依照右端排序
初始兩個陣列：dp放個點到達方法的前綴和，point放每個點的座標；初值為座標0的方法數=1
for each (left,right) of interval do
if right不是point的最後一點 then
將right加入point尾端
將dp的尾端複製加入尾端
在point中二分搜找到left前一點的位置i
將dp[L-2]-dp[i]的值加入dp[L-1]，L是dp目前長度
輸出(dp[L-1]-dp[L-2]+mod)%mod
```
時間複雜度是$O(n\log n)$，因為排序與二分搜。
### C/C++範例程式
這題想到方法後，實作並不困難，二分搜最好可以使用系統內建，執行速度快，好用又不會跳針(出錯)。
一開始先自訂一個struct，用來存一個區間，然後寫一個排序用的比較函數cmp。當然用pair也可以，把右端放前面，也不必寫cmp。第16 ~ 19行根據題目的輸入格式，讀入區間後，進行排序。第20行我們用vector來放dp與point陣列，初值
設dp[0]=1, point[0]=0，也就是在座標0(起點)的到達數是1，此處型態使用long long，避免運算過程溢位。
接著開始歷遍每一個區間，第22行的if是進來的右端點與point最後一點不同，是個新加入的點，所以在point與dp的尾端新增一筆，因為dp是prefix sum所以將前一點的值先記入。然後我們要計算區間和，如果左端是0，就是前面的全部總和，否則以二分搜找左端，這裡二分搜用的是lower_bound再減1。
最後在輸出答案時，因為存的是前綴和，所以挑出最後兩項來相減，記得因為要取餘數，相減後可能是負值，所以把它加上mod後再取餘數。
```cpp=
// number of way to go from 0 to m. DP + prefix sum + binary search
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct SEG {
int left, right;
};
// sort by right
bool cmp(SEG &x, SEG &y) {
return x.right < y.right;
}
int main() {
int n, i,j,m,t;
int mod=1000000007;
scanf("%d%d%d",&n,&m,&mod);
vector<SEG> seg(n);
for (i=0;i<n;i++) scanf("%d",&seg[i].left);
for (i=0;i<n;i++) scanf("%d",&seg[i].right);
sort(seg.begin(), seg.end(), cmp);
vector<ll> dp({1}),point({0}); // init dp[] and point[]
for (SEG s: seg) {
if (point.back() != s.right) { // new right, different from previous
point.push_back(s.right);
dp.push_back(dp.back()); // dp is prefix sum, copy prev sum
}
if (s.left==0) {
dp.back() = (dp.back()+dp[dp.size()-2])%mod;
} else {
i = lower_bound(point.begin(),point.end(),s.left)-point.begin()-1;
dp.back() = (dp.back()+dp[dp.size()-2]-dp[i]+mod)%mod;
}
}
ll ans;
if (point.back() != m) {
ans = 0;
} else ans = (dp.back()-dp[dp.size()-2]+mod)%mod;
printf("%lld\n",ans);
return 0;
}
```
### Python範例程式
以下是Python的寫法。這題想到方法後，實作並不困難，二分搜最好可以使用系統內建，執行速度快，好用又不會跳針(出錯)。第一行的import是為了要呼叫內建的二分搜。
第2 ~ 4行根據題目的輸入格式，讀入區間後，第5行用zip將兩個欄位合併並進行排序，我們把右端放在前面，這樣排序時就是依照右端排序。
第6行我們初設兩個list放dp與point，初值設
dp[0]=1, point[0]=0，
也就是在座標0(起點)的到達數是1。
接著開始歷遍每一個區間，第8行的if是進來的右端點與point最後一點不同，是個新加入的點，所以在point與dp的尾端新增一筆，因為dp是prefix sum所以將前一點的值先直接記入。然後我們要計算區間和，如果左端是0，就是前面的全部總和，否則以二分搜找左端，這裡二分搜用的是bisect_left再減1，bisect_left是bisect中的函數，會找到第一個>= key值的index。
最後是輸出答案時，因為存的是前綴和，所以挑出最後兩項來相減，記得因為要取餘數，Python負數取餘數會回到[0,mod-1]的範圍，所以其實不需要把它加上mod後再取餘數，不過如果有時候會忘記的話，加上不妨。
```python=
from bisect import *
n,m,mod = [int(x) for x in input().split()]
le = [int(x) for x in input().split()]
ri = [int(x) for x in input().split()]
seg = sorted(zip(ri,le)) # (right,left), sorted by right
dp,point = [1],[0] # prefix sum of dp and last point
for right,left in seg:
if point[-1] != right: # new right, different from previous
point.append(right)
dp.append(dp[-1]) # copy previous sum
if left==0:
dp[-1] = (dp[-1]+dp[-2])%mod;
else:
i = bisect_left(point,left)-1
dp[-1] = (dp[-1]+dp[-2]-dp[i]+mod)%mod
if point[-1] != m: ans = 0
else: ans = (dp[-1]-dp[-2]+mod)%mod
print(ans)
```
**End**
Sign in with Wallet
Connect another wallet