# APCS實作題2022年10月第4題：蓋步道 > 日期：2024年8月13日 > 作者：王一哲 > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=j125) ## 題目 ### 問題描述 有一個大小為 $n \times n$ 的方形區域，$h_{ij}$ 代表位於座標 $(i, j)$ 的格子該處的海拔高度。 工程團隊想要從該區域的左上角 $(1, 1)$ 鋪設一條步道到右下角 $(n, n)$，鋪設的步道可以視為在該區域內上下左右四個方向從左上角走到右下角的一條路徑。 考量到行人在步道上行走的安全，必須要注意步道每一步之間的高低落差，並希望可以建立出一個最大高度差最小的步道鋪設方案。 <br /> ### 輸入說明 第一行為一個數字 $n ~(1 \leq n \leq 300)$，代表該區域的大小。 接下來有 $n$ 行，第 $i$ 行有 $n$ 個正整數，每一個正整數 $h_{ij} ~(1 \leq h_{ij} \leq 10^6)$ 代表該位置的海拔高度。 子題配分 - 20%：$n \leq 10$，高度不超過 $10$ - 20%：$n \leq 300$，高度不超過 $10^3$ - 60%：$n \leq 300$，高度不超過 $10^6$ <br /> ### 輸出格式 輸出兩行，第一行輸出鋪設方案中最大高度差的最小值，第二行輸出在該最大高度差下從左上走到右下的最短路徑長度。 <br /> ### 範例輸入 ``` 4 9 4 3 2 5 9 8 10 3 3 2 8 6 3 3 4 ``` ### 範例輸出 ``` 4 6 ``` <br /><br /> ## Python 程式碼 費時最久約為 3.7 s，使用記憶體最多約為 103.3 MB，通過測試。 ```python= n = int(input()) # 讀取地圖維度 n grid = [] # 儲存地圖資料的二維串列 for i in range(n): # 讀取 n 行資料 grid.append(list(map(int, input().split()))) # 讀取一行資料 grid[i].append(0) # 在每一行最後面加上 0 作為哨兵 grid.append([0]*(n+1)) # 在最後新增一行 0 作為哨兵 def bfs(m): # 自訂函式 bfs，代入指定的高度差測試是否能到達終點 visited = [[False]*(n+1) for _ in range(n+1)] # 走訪狀態，(n+1)*(n+1) 的串列 st = [(0, 0, 0)] # 待走訪的位置，資料為 (x 座標, y 座標, 步數) head = 0 # 由 st 讀取資料的索引值 while head < len(st): # 當 head 還沒有出界時繼續執行 r, c, s = st[head]; head += 1 # 由 st 讀取 r, c, s，更新 head visited[r][c] = True # (r, c) 已走訪 for dr, dc in ((0, 1), (-1, 0), (0, -1), (1, 0)): # 4 方向檢測 nr, nc = r + dr, c + dc # 要檢測的位置 (nr, nc) # 如果 (nr, nc) 已走訪、遇到哨兵或是高度差大於 m，繼續檢測下一個 if visited[nr][nc] or grid[nr][nc] == 0 or abs(grid[nr][nc] - grid[r][c]) > m: continue visited[nr][nc] = True # (nr, nc) 已走訪 if nr == n-1 and nc == n-1: return s+1 # 如果走到終點，回傳以 m 為高度差限制對應的步數 s+1 st.append((nr, nc, s+1)) # 還沒有走到終點，將 (nr, nc, s+1) 加入 st return -1 # 如果跑完 while 迴圈還沒有走到終點，回傳 -1 low, high = 0, 10000000 # 高度差下限、上限 while high - low > 1: # 繼續執行的條件，結束時 high 為最小的高度差 mid = (high - low) // 2 + low # 要找到中間值，如果寫成 mid = (high + low) // 2 在 C++ 可能會溢位 steps = bfs(mid) # 呼叫 bfs，代入 mid 找對應的步數 steps if steps != -1: high = mid # 走到終點，降低 high，找更小的高度差 else: low = mid # 走不到終點，提高 low，找更大的高度差 print("{:d}\n{:d}".format(high, bfs(high))) # 印出 high 及對應的步數 ``` <br /><br /> ## C++ 程式碼 費時最久約為 0.2 s，使用記憶體最多約為 1.7 MB，通過測試。 ```cpp= #include <iostream> #include <vector> #include <cmath> #include <queue> typedef long long LL; using namespace std; LL bfs(LL m, vector<vector<LL>> g) { // 自訂函式 bfs，代入指定的高度差測試是否能到達終點 LL n = (LL)g.size()-2; vector<vector<bool>> visited (n+2, vector<bool> (n+2, false)); // 走訪狀態，(n+2)*(n+2) 的陣列 queue<vector<LL>> st; st.push({1, 1, 0}); // 待走訪的位置，資料為 (x 座標, y 座標, 步數) LL ds[4][2] = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}}; // 4 方向檢測用的陣列 while(!st.empty()) { // 當 st 還有資料時繼續執行 LL r = st.front()[0], c = st.front()[1], s = st.front()[2]; // 由 st 讀取 r, c, s st.pop(); // 移除第一筆資料 visited[r][c] = true; // (r, c) 已走訪 for(int i=0; i<4; i++) { // 4 方向檢測 LL nr = r + ds[i][0], nc = c + ds[i][1]; // 要檢測的位置 (nr, nc) // 如果 (nr, nc) 已走訪、遇到哨兵或是高度差大於 m，繼續檢測下一個 if (visited[nr][nc] || g[nr][nc] == 0 || abs(g[nr][nc] - g[r][c]) > m) continue; if (nr == n && nc == n) return s+1; // 如果走到終點，回傳以 m 為高度差限制對應的步數 s+1 visited[nr][nc] = true; // (nr, nc) 已走訪 st.push({nr, nc, s+1}); // 還沒有走到終點，將 (nr, nc, s+1) 加入 st } } return -1; // 如果跑完 while 迴圈還沒有走到終點，回傳 -1 } int main() { int n; cin >> n; // 讀取地圖維度 n vector<vector<LL>> grid (n+2, vector<LL> (n+2, 0)); // 儲存地圖資料的二維陣列 for(int i=1; i<=n; i++) // 讀取地圖資料，由於四周加上 0 作為哨兵，i、j 要從 1 ~ n for(int j=1; j<=n; j++) cin >> grid[i][j]; LL low = 0, high = 10000000; // 高度差下限、上限 while(high - low > 1) { // 繼續執行的條件，結束時 high 為最小的高度差 LL mid = (high - low) / 2 + low; // 要找到中間值，如果寫成 mid = (high + low) / 2 在 C++ 可能會溢位 LL steps = bfs(mid, grid); // 呼叫 bfs，代入 mid 找對應的步數 steps if (steps != -1) high = mid; // 走到終點，降低 high，找更小的高度差 else low = mid; // 走不到終點，提高 low，找更大的高度差 } cout << high << "\n" << bfs(high, grid) << "\n"; // 印出 high 及對應的步數 return 0; } ``` <br /><br /> --- ###### tags:`APCS`、`Python`、`C++`