# APCS實作題2021年11月第2題：動線安排 > 日期：2023年9月21日 > 作者：王一哲 > 題目來源：110年11月實作題第2題 > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=g596) <br /> ## 題目 ### 問題描述 你是一個遊樂園展場的管理員，展場是一個 $m \times n$ 的矩形，可以使用木樁和線來排動線，你可以有兩種操作 - 加入木樁 r c 0。加一木樁在 $(r, c)$，並且向他的上下左右盡量找離最近的木樁連線，題目保證 $(r, c)$ 上一定沒有木樁，若有線經過則先將那些線拆掉後再來連線。 - 移除木樁 r c 1。拔掉位在 $(r, c)$ 上的木樁，並把他的線也拔掉，題目保證 $(r, c)$ 上一定有木樁。 總共有 $h$ 次操作，輸出過程中有線和有木樁佔據空間的面積最大是多少，以及 $h$ 次操作後有線和有木樁佔據空間的面積。 **註：連線可以交叉，一格上可能有兩個方向的連線。** <br /> ### 輸入說明 第一行輸入三個正整數 $m$、$n$ 和 $h$ 代表展場範圍是 $m \times n$，並且有 $h$ 筆操作。 接下來會有 $h$ 行，每一行都有三個非負整數 $r$、$c$、$t$，代表在位置 $(r, c)$ 執行操作 $t$。 數字範圍 - $1 \leq m, n \leq 100$ - $1 \leq h \leq 200$ 子題配分 - 50%：$m = 1$ - 50%：無額外限制 <br /> ### 輸出說明 輸出兩個數字，第一個數字表示，操作過程中有線和有木樁佔據空間的面積最大值；第二個數字表示，操作結束後有線和有木樁佔據空間的面積。 <br /> ### 範例一：輸入 ``` 3 5 6 0 0 0 0 2 0 2 2 0 2 0 0 2 4 0 2 2 1 ``` ### 範例一：正確輸出 ``` 10 6 ``` ### 範例一：運算過程 用 @ 代表柱子，\* 代表連線，_ 代表沒有東西。 ```cpp add (0, 0) @____ _____ _____ add (0, 2) @*@__ _____ _____ add (2, 2) @*@__ __*__ __@__ add (2, 0) @*@__ *_*__ @*@__ add (2, 4) @*@__ *_*__ @*@*@ remove (2, 2) @*@__ *____ @___@ ``` <br /><br /> ### 範例二：輸入 ``` 5 5 7 2 2 0 2 4 0 4 4 0 4 0 0 0 3 0 4 3 0 4 3 1 ``` ### 範例二：正確輸出 ``` 12 7 ``` <br /> ### 範例二：運算過程 用 @ 代表柱子，\* 代表連線，_ 代表沒有東西。 ```cpp add (2, 2) _____ _____ __@__ _____ _____ add (2, 4) _____ _____ __@*@ _____ _____ add (4, 4) _____ _____ __@*@ ____* ____@ add (4, 0) _____ _____ __@*@ ____* @***@ add (0, 3) ___@_ _____ __@*@ ____* @***@ add (4, 3) ___@_ ___*_ __@*@ ___** @**@@ remove (4, 3) ___@_ _____ __@*@ ____* @___@ ``` <br /><br /> ## Python 程式碼 ### 版本1：測試解題想法是否可行，但是程式碼太長 以下的程式碼太長，需要刪除佔了整行的註解，才能在 ZeroJudge 上測試。於 ZeroJudge 測試結果，最長運算時間約為 44 ms，使用記憶體最多約為 3.8 MB，通過測試。 ```python= m, n, h = map(int, input().split()) # 讀取m, n, h maps = [[0]*n for _ in range(m)] # 沒有東西為0，木樁為1，横向連線為2，縱向連線為3，同時有兩個方向的連線為4 ans = 0 # 記錄木樁和連線所佔格子數量 maxAns = 0 # 記錄木樁和連線所佔格子數量最大值 """ 主要解題過程 """ for _ in range(h): # 共執行h次 r, c, t = map(int, input().split()) # 讀取r, c, t """ 如果t為0，於 (r, c) 加上木樁 """ if t == 0: if maps[r][c] == 0: # 如果 (r, c) 是空的 ans += 1 # 木樁和連線所佔格子數量加1 maps[r][c] = 1 # 將 (r, c) 設定為1 between = [] # 記錄兩根木樁之間的格子座標 linked = False # 加進來的木樁是否與另一根木樁連線 """ 檢查加入的木椿上方是否有另一根木樁 """ for i in range(r-1, -1, -1): if maps[i][c] == 1: # 如果遇到另一根木樁 linked = True # linked 設定為 True break # 中止迴圈 else: # 如果這個格子不是木樁 between.append([i, c]) # 將這個格子的座標加入串列 between if linked: # 如果加入的木樁與另一根木樁連線 for b in between: # 取出兩根木樁之間的格子座標 if maps[b[0]][b[1]] == 0: # 如果這格是空的 maps[b[0]][b[1]] = 3 # 於這個格子加上縱向連線 ans += 1 # 木樁和連線所佔格子數量加1 elif maps[b[0]][b[1]] == 2: # 如果這格有横向連線 maps[b[0]][b[1]] = 4 # 將這格改成兩個方向的連線 """ 清空資料及重設變數 """ between.clear() # 清空串列 between linked = False # 連線狀態重設為 False """ 檢查加入的木椿下方是否有另一根木樁 """ for i in range(r+1, m): if maps[i][c] == 1: # 如果遇到另一根木樁 linked = True # linked 設定為 True break # 中止迴圈 else: # 如果這個格子不是木樁 between.append([i, c]) # 將這個格子的座標加入串列 between if linked: # 如果加入的木樁與另一根木樁連線 for b in between: # 取出兩根木樁之間的格子座標 if maps[b[0]][b[1]] == 0: # 如果這格是空的 maps[b[0]][b[1]] = 3 # 於這個格子加上縱向連線 ans += 1 # 木樁和連線所佔格子數量加1 elif maps[b[0]][b[1]] == 2: # 如果這格有横向連線 maps[b[0]][b[1]] = 4 # 將這格改成兩個方向的連線 """ 清空資料及重設變數 """ between.clear() # 清空串列 between linked = False # 連線狀態重設為 False """ 檢查加入的木椿左側是否有另一根木樁 """ for i in range(c-1, -1, -1): if maps[r][i] == 1: # 如果遇到另一根木樁 linked = True # linked 設定為 True break # 中止迴圈 else: # 如果這個格子不是木樁 between.append([r, i]) # 將這個格子的座標加入串列 between if linked: # 如果加入的木樁與另一根木樁連線 for b in between: # 取出兩根木樁之間的格子座標 if maps[b[0]][b[1]] == 0: # 如果這格是空的 maps[b[0]][b[1]] = 2 # 於這個格子加上横向連線 ans += 1 # 木樁和連線所佔格子數量加1 elif maps[b[0]][b[1]] == 3: # 如果這格有縱向連線 maps[b[0]][b[1]] = 4 # 將這格改成兩個方向的連線 """ 清空資料及重設變數 """ between.clear() # 清空串列 between linked = False # 連線狀態重設為 False """ 檢查加入的木椿右側是否有另一根木樁 """ for i in range(c+1, n): if maps[r][i] == 1: # 如果遇到另一根木樁 linked = True # linked 設定為 True break # 中止迴圈 else: # 如果這個格子不是木樁 between.append([r, i]) # 將這個格子的座標加入串列 between if linked: # 如果加入的木樁與另一根木樁連線 for b in between: # 取出兩根木樁之間的格子座標 if maps[b[0]][b[1]] == 0: # 如果這格是空的 maps[b[0]][b[1]] = 2 # 於這個格子加上横向連線 ans += 1 # 木樁和連線所佔格子數量加1 elif maps[b[0]][b[1]] == 3: # 如果這格有縱向連線 maps[b[0]][b[1]] = 4 # 將這格改成兩個方向的連線 """ 如果t為1，移除 (r, c) 的木樁 """ if t == 1: maps[r][c] = 0 # 將 (r, c) 設定為0 between = [] # 記錄兩根木樁之間的格子座標 linked = False # 被移除的木樁是否與另一根木樁連線 ans -= 1 # 木樁和連線所佔格子數量減1 """ 檢查被移除的木椿上方是否有另一根木樁 """ for i in range(r-1, -1, -1): if maps[i][c] == 1: # 如果遇到另一根木樁 linked = True # linked 設定為 True break # 中止迴圈 elif maps[i][c] == 3 or maps[i][c] == 4: # 如果格子上有縱向或兩個方向的連線 between.append([i, c]) # 將這個格子的座標加入串列 between if linked: # 如果被移除的木樁與另一根木樁連線 for b in between: # 取出兩根木樁之間的格子座標 if maps[b[0]][b[1]] == 3: # 如果此格是縱向連線 maps[b[0]][b[1]] = 0 # 拆掉連線，將此格設定為0 ans -= 1 # 木樁和連線所佔格子數量減1 elif maps[b[0]][b[1]] == 4: # 如果此格是兩個方向的連線 maps[b[0]][b[1]] = 2 # 只剩下横向連線 """ 清空資料及重設變數 """ between.clear() # 清空串列 between linked = False # 連線狀態重設為 False """ 檢查被移除的木椿下方是否有另一根木樁 """ for i in range(r+1, m): if maps[i][c] == 1: # 如果遇到另一根木樁 linked = True # linked 設定為 True break # 中止迴圈 elif maps[i][c] == 3 or maps[i][c] == 4: # 如果格子上有縱向或兩個方向的連線 between.append([i, c]) # 將這個格子的座標加入串列 between if linked: # 如果被移除的木樁與另一根木樁連線 for b in between: # 取出兩根木樁之間的格子座標 if maps[b[0]][b[1]] == 3: # 如果此格是縱向連線 maps[b[0]][b[1]] = 0 # 拆掉連線，將此格設定為0 ans -= 1 # 木樁和連線所佔格子數量減1 elif maps[b[0]][b[1]] == 4: # 如果此格是兩個方向的連線 maps[b[0]][b[1]] = 2 # 只剩下横向連線 """ 清空資料及重設變數 """ between.clear() # 清空串列 between linked = False # 連線狀態重設為 False """ 檢查被移除的木椿左側是否有另一根木樁 """ for i in range(c-1, -1, -1): if maps[r][i] == 1: # 如果遇到另一根木樁 linked = True # linked 設定為 True break # 中止迴圈 elif maps[r][i] == 2 or maps[r][i] == 4: # 如果格子上有横向或兩個方向的連線 between.append([r, i]) # 將這個格子的座標加入串列 between if linked: # 如果被移除的木樁與另一根木樁連線 for b in between: # 取出兩根木樁之間的格子座標 if maps[b[0]][b[1]] == 2: # 如果此格是横向連線 maps[b[0]][b[1]] = 0 # 拆掉連線，將此格設定為0 ans -= 1 # 木樁和連線所佔格子數量減1 elif maps[b[0]][b[1]] == 4: # 如果此格是兩個方向的連線 maps[b[0]][b[1]] = 3 # 只剩下縱向連線 """ 清空資料及重設變數 """ between.clear() # 清空串列 between linked = False # 連線狀態重設為 False """ 檢查被移除的木椿右側是否有另一根木樁 """ for i in range(c+1, n): if maps[r][i] == 1: # 如果遇到另一根木樁 linked = True # linked 設定為 True break # 中止迴圈 elif maps[r][i] == 2 or maps[r][i] == 4: # 如果格子上有横向或兩個方向的連線 between.append([r, i]) # 將這個格子的座標加入串列 between if linked: # 如果被移除的木樁與另一根木樁連線 for b in between: # 取出兩根木樁之間的格子座標 if maps[b[0]][b[1]] == 2: # 如果此格是横向連線 maps[b[0]][b[1]] = 0 # 拆掉連線，將此格設定為0 ans -= 1 # 木樁和連線所佔格子數量減1 elif maps[b[0]][b[1]] == 4: # 如果此格是兩個方向的連線 maps[b[0]][b[1]] = 3 # 只剩下縱向連線 maxAns = max(maxAns, ans) # 更新木樁和連線所佔格子數量最大值 """ 除錯用，印出目前的地圖 """ """for i in range(m): for j in range(n): print(maps[i][j], end=" " if j < n-1 else "\n")""" """ 除錯用，印出木樁和連線所佔格子數量最大值及目前所佔格子數 """ #print("max = {:d}, area = {:d}".format(maxAns, ans)) """ 印出答案 """ print(maxAns) print(ans) ``` <br /><br /> ### 版本2：解題想法與版本1相同，但是用自訂函式減少程式碼行數 於 ZeroJudge 測試結果，最長運算時間約為 38 ms，使用記憶體最多約為 3.7 MB，通過測試。 ```python= m, n, h = map(int, input().split()) # 讀取m, n, h maps = [[0]*n for _ in range(m)] # 沒有東西為0，木樁為1，横向連線為2，縱向連線為3，同時有兩個方向的連線為4 ans = 0 # 記錄木樁和連線所佔格子數量 maxAns = 0 # 記錄木樁和連線所佔格子數量最大值 """ 自訂函式：加入木樁時檢查縱向是否有其它木樁或連線 """ def checkCol(c, ri, rf, d): global maps, ans between = [] # 記錄兩根木樁之間的格子座標 linked = False # 加進來的木樁是否與另一根木樁連線 for i in range(ri, rf, d): if maps[i][c] == 1: # 如果遇到另一根木樁 linked = True # linked 設定為 True break # 中止迴圈 else: # 如果這個格子不是木樁 between.append([i, c]) # 將這個格子的座標加入串列 between if linked: # 如果加入的木樁與另一根木樁連線 for b in between: # 取出兩根木樁之間的格子座標 if maps[b[0]][b[1]] == 0: # 如果這格是空的 maps[b[0]][b[1]] = 3 # 於這個格子加上縱向連線 ans += 1 # 木樁和連線所佔格子數量加1 elif maps[b[0]][b[1]] == 2: # 如果這格有横向連線 maps[b[0]][b[1]] = 4 # 將這格改成兩個方向的連線 """ 自訂函式：加入木樁時檢查橫向是否有其它木樁或連線 """ def checkRow(r, ci, cf, d): global maps, ans between = [] # 記錄兩根木樁之間的格子座標 linked = False # 加進來的木樁是否與另一根木樁連線 for i in range(ci, cf, d): if maps[r][i] == 1: # 如果遇到另一根木樁 linked = True # linked 設定為 True break # 中止迴圈 else: # 如果這個格子不是木樁 between.append([r, i]) # 將這個格子的座標加入串列 between if linked: # 如果加入的木樁與另一根木樁連線 for b in between: # 取出兩根木樁之間的格子座標 if maps[b[0]][b[1]] == 0: # 如果這格是空的 maps[b[0]][b[1]] = 2 # 於這個格子加上横向連線 ans += 1 # 木樁和連線所佔格子數量加1 elif maps[b[0]][b[1]] == 3: # 如果這格有縱向連線 maps[b[0]][b[1]] = 4 # 將這格改成兩個方向的連線 """ 自訂函式：移除木樁時檢查縱向是否有其它木樁或連線 """ def removeCol(c, ri, rf, d): global maps, ans between = [] # 記錄兩根木樁之間的格子座標 linked = False # 被移除的木樁是否與另一根木樁連線 for i in range(ri, rf, d): if maps[i][c] == 1: # 如果遇到另一根木樁 linked = True # linked 設定為 True break # 中止迴圈 elif maps[i][c] == 3 or maps[i][c] == 4: # 如果格子上有縱向或兩個方向的連線 between.append([i, c]) # 將這個格子的座標加入串列 between if linked: # 如果被移除的木樁與另一根木樁連線 for b in between: # 取出兩根木樁之間的格子座標 if maps[b[0]][b[1]] == 3: # 如果此格是縱向連線 maps[b[0]][b[1]] = 0 # 拆掉連線，將此格設定為0 ans -= 1 # 木樁和連線所佔格子數量減1 elif maps[b[0]][b[1]] == 4: # 如果此格是兩個方向的連線 maps[b[0]][b[1]] = 2 # 只剩下横向連線 """ 自訂函式：移除木樁時檢查横向是否有其它木樁或連線 """ def removeRow(r, ci, cf, d): global maps, ans between = [] # 記錄兩根木樁之間的格子座標 linked = False # 被移除的木樁是否與另一根木樁連線 for i in range(ci, cf, d): if maps[r][i] == 1: # 如果遇到另一根木樁 linked = True # linked 設定為 True break # 中止迴圈 elif maps[r][i] == 2 or maps[r][i] == 4: # 如果格子上有横向或兩個方向的連線 between.append([r, i]) # 將這個格子的座標加入串列 between if linked: # 如果被移除的木樁與另一根木樁連線 for b in between: # 取出兩根木樁之間的格子座標 if maps[b[0]][b[1]] == 2: # 如果此格是横向連線 maps[b[0]][b[1]] = 0 # 拆掉連線，將此格設定為0 ans -= 1 # 木樁和連線所佔格子數量減1 elif maps[b[0]][b[1]] == 4: # 如果此格是兩個方向的連線 maps[b[0]][b[1]] = 3 # 只剩下縱向連線 """ 主要解題過程 """ for _ in range(h): # 共執行h次 r, c, t = map(int, input().split()) # 讀取r, c, t """ 如果t為0，於 (r, c) 加上木樁 """ if t == 0: if maps[r][c] == 0: # 如果 (r, c) 是空的 ans += 1 # 木樁和連線所佔格子數量加1 maps[r][c] = 1 # 將 (r, c) 設定為1 checkCol(c, r-1, -1, -1) # 檢查加入的木椿上方是否有另一根木樁 checkCol(c, r+1, m, 1) # 檢查加入的木椿下方是否有另一根木樁 checkRow(r, c-1, -1, -1) # 檢查加入的木椿左側是否有另一根木樁 checkRow(r, c+1, n, 1) # 檢查加入的木椿右側是否有另一根木樁 """ 如果t為1，移除 (r, c) 的木樁 """ if t == 1: maps[r][c] = 0 # 將 (r, c) 設定為0 ans -= 1 # 木樁和連線所佔格子數量減1 removeCol(c, r-1, -1, -1) # 檢查被移除的木椿上方是否有另一根木樁 removeCol(c, r+1, m, 1) # 檢查被移除的木椿下方是否有另一根木樁 removeRow(r, c-1, -1, -1) # 檢查被移除的木椿左側是否有另一根木樁 removeRow(r, c+1, n, 1) # 檢查被移除的木椿右側是否有另一根木樁 maxAns = max(maxAns, ans) # 更新木樁和連線所佔格子數量最大值 """ 除錯用，印出目前的地圖 """ """for i in range(m): for j in range(n): print(maps[i][j], end=" " if j < n-1 else "\n")""" """ 除錯用，印出木樁和連線所佔格子數量最大值及目前所佔格子數 """ #print("max = {:d}, area = {:d}".format(maxAns, ans)) """ 印出答案 """ print(maxAns) print(ans) ``` <br /><br /> ___ ###### tags:`APCS`、`Python`