**Chapter 7 (II)**
## 例題與習題
這一節裡面我們提出幾個例題與習題，由於圖論演算法的題目雖多，但大部分超過APCS的範圍，所以這裡只有一些比較簡單的題目。有一些一維與二維陣列的題目其實用圖的概念會更容易了解，我們也放了一些這樣的題目。第一題是一個很簡單的二維陣列走訪的題目，沒有學過圖的也能作答，但用一些技巧會更簡單。
---
##### P-7-3. 機器人走棋盤 (APCS 201906)
有一個方格棋盤的每一個格子裡都標示了一個不同的整數，有一個機器人在此方格棋盤上行動，每一次只會移動到目前位置的上下左右四個相鄰格子其中之一。起點是數字最小的格子，每次移動則在可以移動位置中挑選數字最小的格子，但是走過的格子就不會再走，當無路可走的時候，機器人就會停下來。輸入方格棋盤中每個格子的數字，請模擬機器人走過的路徑，並輸出機器人走過的格子的數字總和。
以下是一個例子，輸入的$4 \times 5$的方格內的數字如圖中所標示。在本例子中，機器人的起點會是1，所走的路徑是 (1, 4, 6, 7, 14, 20, 21, 29, 30)。走到30的時候已經無路可走，所以機器人就停止了，而經過的數字總和是132。
|24 |7 |14 |20 |30|
|-|-|-|-|-|
|11 |6 |4 |21 |29|
|2| 8| 1| 35| 40|
|3 |9 |5 |12|15|
Time limit: 1秒
輸入格式：輸入的第一行是兩個不超過100的正整數$m$ 與 $n$，代表是一個$m \times n$的方格棋盤，接下來有$m$ 行，每行$n$個數字，分別是方格棋盤由上而下，由左而右的數字。方格內的數字皆為不超過1e5的非負整數，同一行數字之間以空白間隔。
輸出：機器人走過的格子中數字的總和。
範例一輸入：
2 7
6 8 7 2 1 4 5
9 3 10 11 12 13 14
範例一輸出：
36
範例二輸入：
4 5
24 7 14 20 30
11 6 4 21 29
2 8 1 35 40
3 9 5 12 15
範例二輸出：
132
範例一說明：機器人走的路線是(1,2,7,8,3,9,6)。
範例二說明：此為題目敘述中的範例。
---
這一題可以分成兩個部分：(1)找出一個二維陣列中的最小值，以該位置為起點；(2)模擬機器人的行走，對於某一個位置，找到上下左右四個鄰居中沒走過的最小值，而且要能辨識是否已經無路可走。第一個部分很簡單，處理二維陣列(矩陣)，我們可以搭配一個雙迴圈歷遍來檢查最小值。為了要模擬機器人的行走位置，我們以一對變數$(r,c)$代表機器人所在位置在第$r$列$c$行，這裡我們採取矩陣行列的定位方式，使用平面座標的定位方式也可以。
為了要避免走到曾經走過的格子，我們可以採用圖形走訪的技巧，利用一個陣列$visit$來記錄哪些格子被走過與否。對於每一個格子，我們找出四個鄰居中的最小值，同時避免走到界外以及走過的點。以下是直接的寫法。
```python=
m, n = map(int, input().split())
mat = []
for i in range(m):
mat.append([int(x) for x in input().split()])
# find minimum
mm = oo = 1000000
for i in range(m):
for j in range(n):
if mat[i][j] < mm:
r=i; c=j; mm=mat[i][j]
#
visit = [[False]*n for i in range(m)]
total = 0
while not visit[r][c]: # current position (r,c)
total += mat[r][c]
visit[r][c] = True
# find min neighbor
mm = oo; nr = r; nc = c
if r>0 and not visit[r-1][c] and mat[r-1][c]<mm:
mm = mat[r-1][c]; nr = r-1; nc = c
if r<m-1 and not visit[r+1][c] and mat[r+1][c]<mm:
mm = mat[r+1][c]; nr = r+1; nc = c
if c>0 and not visit[r][c-1] and mat[r][c-1]<mm:
mm = mat[r][c-1]; nr = r; nc = c-1
if c<n-1 and not visit[r][c+1] and mat[r][c+1]<mm:
mm = mat[r][c+1]; nr = r; nc = c+1
r,c = nr,nc
print(total)
```
這裡我們介紹一些走格子點可以用的小技巧，它不會改善時間複雜度，但有時候可以讓程式更簡潔，執行時間也會稍微好一點。
* 為了預防出界，我們可以在原矩陣的外圍擺一圈虛擬的格子，並將他們都設定成oo，這樣我們的程式碼會比較簡單。對Python來說，不必圍四周，只要圍右邊與下邊就可以了，因為list[-1]是最後一個元素，所以$i=0$時，$[i-1]$也就是最後一個。
* 每次我們要檢查四個鄰居，所以要寫四個if，如果是可以走鄰近八方位的題目則要寫8個if，這實在太囉嗦，所以我們把他寫成迴圈的樣子。請看以下範例程式，我們用了兩個長度為4的陣列dr[]與dc[]，裡面存放的其實是上右下左四個鄰居的列與行位移量。在檢查四個鄰居時，每一個鄰居的位置就是$(r+dr[d], c+dc[d])$。
* 我們使用visit來標記走過的格子，如果格子內的值用完就沒有用的話，也可以採取另外一種方式，就是將走過格子的內容改成oo。
以下是這樣的範例程式。
```python=
m, n = map(int, input().split())
oo = 1000001
dr = [-1,0,1,0]; dc = [0,1,0,-1] # 上右下左
mat = []
for i in range(m):
mat.append([int(x) for x in input().split()]+[oo])
mat.append([oo]*n)
# find minimum
mm = oo
for i in range(m):
for j in range(n):
if mat[i][j] < mm:
r=i; c=j; mm=mat[i][j]
total = 0
while mat[r][c] < oo: # current position (r,c)
total += mat[r][c]
mat[r][c] = oo # update to visited state
mm = oo; nr = r; nc = c
for d in range(4): # find min neighbor
i = r+dr[d]; j = c+dc[d]
if mat[i][j] < mm:
mm = mat[i][j]; nr = i; nc = j
r,c = nr,nc
print(total)
```
很多棋盤上最少走幾步的問題，其實是圖的BFS的一種形式，例如象棋的車、馬、西洋棋的皇后，下面是一個這樣的問題。
---
##### P-7-4. 方格棋盤的最少轉彎數路線
有一個$m\times n$的方格棋盤，每個格子可能是0或1，其中0代表可以通過而1代表不能通過。現在有一個機器人從左上角編號$(1,1)$的格子出發，要到達右下角編號$(m,n)$的格子，每次可以往上下左右四個方向移動，我們要找到轉彎次數最少的路線。
Time limit: 1秒
輸入格式：第一行是兩個正整數$m$與$n$，代表格子棋盤的列數與行數，接下來有$m$行，每行是一個長度為$n$僅由0與1組成的字串，代表方格棋盤由上往下由左至右的內容，出發與目的格子必然是0。$m$與$n$不超過500。
輸出：最少的轉彎數。如果無法到達，則輸出 -1。
範例一輸入：
3 6
001010
101000
100010
範例一輸出：
5
範例二輸入：
3 4
0110
0110
0010
範例二輸出：
-1
---
把每一次轉彎當作走一步，這是最少步數的問題，所以可以用BFS來解。為了方便我們採取上一題類似的手法，在邊界放上不能走的標記，另外定義四個方向的位移，我們以距離dist=-1當成尚未被發現，如此就省下visit陣列的使用。其他就是BFS的作法，停止條件包括可以走的已經走完或是目的位置已經達到。因為本題要計算的是轉彎次數，我們算出來的是移動次數，所以最後答案要減一。
以下是範例程式，時間複雜度是$O((m+n)mn)$，因為有$mn$個點，每個點可能檢查$(m+n)$個位置。
```python=
# P-7-4 minimum turn
m, n = map(int, input().split())
oo = 1000001
dr = [-1,0,1,0]; dc = [0,1,0,-1] # 上右下左
mat = []
for i in range(m):
mat.append(input()+'1') # sentinel at right
mat.append('1'*n) # sentinel at bottom
# bfs
que = [(0,0)]; head = 0
dist = [[-1]*n for i in range(m)] # -1 =unvisited
dist[0][0] = 0
while head < len(que) and dist[m-1][n-1]==-1:
r,c = que[head]; head += 1
for d in range(4): # check 4 direction
nr = r+dr[d]; nc = c+dc[d]
while mat[nr][nc]=='0': # until 1
if dist[nr][nc]<0:
dist[nr][nc] = dist[r][c]+1
que.append((nr,nc))
nr += dr[d]
nc += dc[d]
#
#
if dist[m-1][n-1] >= 0:
dist[m-1][n-1] -= 1
print(dist[m-1][n-1])
```
下一個是BFS在一維數線上的問題，留為習題。
---
##### Q-7-5. 闖關路線 (APCS201910)
某個闖關遊戲上有一隻神奇寶貝與兩個可控制左右移動的按鍵。神奇寶貝被安置在僅可左右移動的滑軌上。滑軌分成$n$個位置，由左到右分別以0 ~ $n – 1$表示。當遊戲開始時，神奇寶貝從位置0開始，遊戲的資訊包含P、L與R三個數字，其中P表示所須移至的目標位置，L與R則分別表示每按一次左鍵或右鍵後，會往左或往右移動的格子數。此外，每一個位置$x$都對應一個瞬間移動位置$S(x)$；每一次按鍵後，神奇寶貝會先依據按鍵往左或右移動到某個位置$x$，接著瞬間移動至$S(x)$。某些點的瞬間移動位置等同原地點，也就是$S(x) = x$，這些點稱為停留點。開始與目標位置都一定是停留點；此外，每個點的瞬間移動位置都一定是停留點(除非超出界外)，也就是不會發生連續瞬間移動的情形。
遊戲的目標是以最少的按鍵數操作神奇寶貝由開始位置到達目標位置，此外，在移動過程中不可以超過滑軌的範圍$[0, n – 1]$，否則算闖關失敗；某些點的瞬間移動位置也可能會超出滑軌的範圍，移動到這些點也會導致闖關失敗。
Time limit: 3 秒
輸入格式：輸入有兩行，第一行有4個數字，第1個為$n$，第2個為目標位置P，第3個為L，第4個為R，後三個數字皆為小於$n$之正整數，且$2 \le n \le 1e6$。第二行有$n$個整數，依序是各點的瞬間移動位置$S(0), S(1), …, S(n – 1)$，這些數字是絕對值不超過1e8的整數。
輸出：輸出到達目標位置所需的最少按鍵數，如果無法到達目標位置，則輸出 –1。
範例一輸入：
5 3 1 2
0 3 2 3 5
範例一輸出：
2
範例二輸入：
10 8 2 3
0 5 2 3 4 5 6 6 8 9
範例二輸出：
3
範例一說明：位置區間為[0,4]，目標位置為3，左鍵往左移動1格，右鍵往右移動2格。到目標位置最少的按鍵數是2次：從起點0第一次按下右鍵會到達位置2，因為$S(2)=2$，因此停留在2，第二次按下左鍵，會往左移一格到達1，因為$S(1)=3$，所以瞬間移動到3，由於3是目標位置，所以就闖關成功了。
範例二說明：位置區間為[0,9]，目標位置為8，按一次左鍵往左移動2格，按一次右鍵往右移動3格。到達目標位置的最少按鍵數是3次，其經過的路徑是：
0，按右鍵-> 3 (停留在3)，按左鍵-> 1 (瞬間移動到5)，按右鍵-> 8 (停留在8，到達)。
---
Q-7-5提示：在一條數線上，每次按左鍵可以目前位置移動到某處，按右鍵可以到達某處。要計算從起點到終點最少要按幾次鍵。起點固定在0的位置，而終點則是輸入時給定。移動的規則是：按下右鍵往右移 R 格，按下左鍵往左移 L格，此外，每次按鍵後移動到位置 $x$ 時，會立刻移動到 $S(x)$。
如果沒有瞬間移動，這一題幾乎是問$xR-yL=P$的最小$x+y$整數解，我們這裡不探討數學問題，在有瞬間移動的狀況下，要以計算來完成求解。他顯然是BFS的退化在一維數線上的狀況，基本上我們算出一步(一次按鍵)可以到達的點，然後算兩步的點，…，直到走到目標或是無路可走為止，甚至不需要了解 BFS 也可以推想出作法，但是有BFS的知識讓我們可以很容易的作出標準作法。
### DAG上的路徑問題
借用下一個例題，我們來學習一下DAG的路徑長度問題。圖的路徑長度問題是一群重要的問題，典型的題目是找最短路徑或最長路徑，根據圖的性質與條件，問題的難度不一，須要使用不同的演算法。目前為止我們會使用BFS計算無加權圖的最短路徑，如果邊上有權重(長度)，那麼BFS無法求得正確的解，但是對於DAG，我們可以是用類似BFS的方法計算出最長與最短路徑。我們先以最短路徑為例，最長路徑的做法是相同的，這裡的最長路徑是指最長的簡單路徑。
假設要計算DAG $G=(V,E,w)$上某點$s$到$t$的最短路徑。對任一點$v$，令$d[v]$是$s$到$v$的最短路徑長度，回想一下在動態規劃時的狀態轉移，我們可以知道，$d[s]=0$；而對於$v != s$，
$d[v]=min\{d[u]+w(u,v): \forall (u,v) \in E\}$
其中這些$u$就是$v$的前置狀態。這其實只是一種很簡單的DP，類似於P-6-6(方格棋盤路線)中從左上走到右下的最大權重路線，只是只能往右往下的棋盤是一個很簡單的DAG。有了這個遞迴式之後，計算的方向就是DAG的拓樸順序，所以只要找到拓樸順序後，計算$d[]$值就可以了，另外，也可以一面找拓樸順序一面計算$d[]$。
---
##### P-7-6. DAG的最長與最短路徑
輸入一個DAG以及$s$與$t$兩點，計算$s$到$t$的最短與最長簡單路徑的長度。兩點之間可能有多個邊。
Time limit: 2秒
輸入格式：第一行是兩個正整數$n$與$m$，代表點數與邊數，點以0 ~ $n-1$編號，第二行兩個整數$s$與$t$，接下來有$m$行，每行三個整數 $u, v, w$ 代表一條有向邊$(u,v)$的長度是$w$。$n$不超過1e4，$m$不超過1e5, $w$的絕對值不超過1e4。輸入保證是個DAG。
輸出：第一行輸出最短路徑長度，第二行輸出最長路徑長度，如果不存在，兩者皆輸出”No path”。
範例一輸入：
5 6
0 4
0 2 3
0 3 1
2 1 -2
3 4 0
1 4 2
2 4 3
範例一輸出：
1
6
範例二輸入：
4 3
2 0
2 1 5
1 3 0
0 1 1
範例二輸出：
No path
No path
---
以下的範例程式中，我們採取一回合式的做法，也就是找拓樸順序的同時，就進行最短與最長路徑的計算。程式與前面計算拓樸順序的範例程式很像，不過這裡因為邊是有加權長度的，所以在儲存圖的鄰接串列時，我們需要儲存鄰居的編號以及到達該鄰居的邊長，程式中採用的方式是$adj[v]$中有$(u,w)$表示$v$有一根到$u$的邊長度為$w$。因為要計算最短與最長距離，我們用$mind[v]$與$maxd[v]$代表起點s到達$v$點的最短與最長距離，只要跟著拓樸順序來作DP就可以了。
要留意的是起點的in-degree不一定是0，而in-degree為0的點是起點到達不了的(除了起點)，我們可以把這些點的距離設為無窮大，計算時只計算非無窮大的距離，這樣就可以辨別是否有路徑。
```python=
# P-7-6 longest and shortest path on dag O(m+n), non-recursive
n, m = map(int, input().split())
source, goal = map(int, input().split())
adj = [[] for i in range(n)] # (out neighbor,length)
deg = [0]*n # in-degree
for i in range(m):
u,v,w = map(int, input().split())
adj[u].append((v,w))
deg[v] += 1
oo = 10**9
mind = [oo]*n # min distance
maxd = [-oo]*n # max distance
mind[source] = maxd[source] = 0
# push all indeg==0
que = [v for v in range(n) if deg[v]==0]
head = 0
while head < len(que): # until queue is empty
v = que[head]; head += 1
for u,w in adj[v]:
if mind[v] < oo: # path exists
mind[u] = min(mind[u], mind[v] + w)
maxd[u] = max(maxd[u], maxd[v] + w)
deg[u] -= 1
if deg[u] ==0: que.append(u)
#
# output
if mind[goal] == oo:
print("No path\nNo path")
else:
print(mind[goal])
print(maxd[goal])
```
我們當然也可以用top-down的DP，寫成遞迴的樣子，以下是範例程式。為了進行遞迴呼叫，我們儲存邊的方式是存in-neighbor，也就是存每個點的前置點有哪些。其他部分就只是簡單的top-down DP的寫法，我們將找mind[]與maxd[]寫在一個函式中。
```python=
# P-7-6 longest and shortest path on dag O(m+n), recursive
n, m = map(int, input().split())
source, goal = map(int, input().split())
pred = [[] for i in range(n)] # (in neighbor,length)
for i in range(m):
u,v,w = map(int, input().split())
pred[v].append((u,w))
oo = 10**9
mind = [oo+1]*n # min distance, oo+1 as uncomputed
maxd = [-oo-1]*n # max distance
mind[source] = maxd[source] = 0
def dfind(v): # return min and max distance
if mind[v]<=oo: return mind[v],maxd[v]
imin, imax = oo,-oo
for u,w in pred[v]:
p,q = dfind(u)
if p<oo:
imin = min(imin,p+w)
imax = max(imax,q+w)
mind[v],maxd[v] = imin,imax
return imin,imax
# output
p,q = dfind(goal)
if p == oo:
print("No path\nNo path")
else:
print(p,q,sep='\n')
```
以下一個題目是DAG在計劃管理上的應用，AOV是Activity On Vertex的縮寫，我們留做習題。
---
##### Q-7-7. AOV最早完工時間
某個計劃有$n$項工作，以1 ~ $n$編號，工作之間有前置關係，我們用一個點代表一項工作，以邊$(a,b)$表示$a$是$b$的前置工作，也就是說$a$完成之後，工作$b$才能開始。每一項工作v有一個需求的工作時間$w[v]$，代表該工作至少需要耗時$w[v]$才能完成。
本題要計算此計畫的最早完工時間，也就是計畫開始後，最早可以完成所有工作的時間。此外，對於某個工作，如果該工作的任何延誤都會讓整個計畫的最早完工時間延後，這個工作就稱為關鍵工作，否則稱為非關鍵工作。請計算那些工作是關鍵工作。
舉例來說，$n=3$，前置關係有$(1,3)$與$(2,3)$，代表工作1完成後才可以開始工作3，相同的，工作2完成後才可以開始工作3。需求工時為$w[1]=1$, $w[2]=3$, $w[3]=4$。我們可以看得出，工作1與2可以一起開始平行作業，在時間1時可以完成工作1，時間3時可以完成工作2，因此工作3最早可以開始的時間是3，而最早的完工時間是7。這三項工作中，工作2與3是關鍵工作，但工作1不是，因為工作1只要不花超過3的工時(延誤超過2)，並不會影響整個計劃的最早完工時間。
Time limit: 2 秒
輸入格式：第一行是兩個正整數$n$與$m$，代表工作數與前置關係數，點以1 ~ $n$編號，第二行是$n$個正整數，依序代表每一個工作的需求工時$w[v]$，接下來有$m$行，每行兩個整數$u$與 $v$，代表$u$是$v$的前置工作。$n$不超過1e4，$m$不超過1e5，$w$不超過1e3。輸入保證有解。
輸出：第一行輸出最早完工時間，第二行輸出那些工作是關鍵工作，輸出時依照工作的編號由小到大，相鄰兩數字之間以一個空白分格。
範例一輸入：
3 2
1 3 4
1 3
2 3
範例一輸出：
7
2 3
範例二輸入：
4 4
1 2 3 4
1 2
1 3
1 4
3 4
範例二輸出：
8
1 3 4
---
下一個也是習題。
---
##### Q-7-8. 小寶的著色問題
小寶有個布娃娃，娃娃會變化。娃娃身上有一些圖案，這些圖案是由一些圓圈和一些線條組成，每個線條連接著某兩個不同的圓圈。小寶很喜歡著色，他決定要把這些圓圈塗上紅色或藍色，他覺得有線條相連的圓圈最好塗上不一樣的顏色，但是因為圓圈很多，他不知道能不能夠完成這樣的想法，請你幫他計算看看是否可以有辦法完成這樣的著色。
Time limit: 5秒
輸入格式：第一行有一個整數Ｔ，代表接下來有Ｔ張圖的資料要計算。每張圖資料的第一行是兩個整數$n$與$m$，代表有$n4個圓圈與$m$個線條，第二行有$2m$個整數，每兩個一組代表一根線條所連接的兩個圓圈編號，圓圈是以0 ~ $n-1$編號。$n$不超過1e4，$m$不超過1e5。T不超過20。
輸出：依序每一行輸出一張圖是否可以正確著色，如果是，則輸出yes，否則輸出no。
範例一輸入：
2
2 0
4 3
0 3 3 2 2 0
範例一輸出：
yes
no
範例說明：第一張圖$n=2$, $m=0$，表示有兩個圓圈而沒有線條，可以正確著色。第二張圖有4個圓圈與3根線條，3根線條是(0,3)、(3,2)與(2,0)，這3個點如果只用2種顏色，不管如何上色都會有同色的相連。
---
提示：把圓圈看成圖的點，線條看成邊。每個點與他的鄰居必須不同色，我們可以用BFS或DFS做圖的走訪與著色，過程中檢查是否有衝突發生。
**End of Chapter 7 (II)**
接續 [AP325-Python 第7章 基本圖論演算法 (III)](/MvQdyDLxTnqcsmoP8KkfQw)
Sign in with Wallet
Connect another wallet