平緩步道 題解｜APCS 2022 年 10 月高級 第 4 題

前置知識

這題是「對答案二分搜」加「方格圖 BFS」，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

  • 方格圖上的 BFS：NTUCPC Guide〈廣度優先搜尋〉（例題「流水問題」就是方格 BFS）、吳邦一《AP325》7.2.2（教材 PDF 第 225～228 頁）——第一次走到就是最少步數；會用到方向表與邊界判斷。
  • 對答案二分搜：NTUCPC Guide〈對答案二分搜〉、AP325 4.2.4「外掛二分搜」（教材 PDF 第 126～128 頁）——先寫「坡度上限給定時走不走得到」，再對坡度二分。
  • Dijkstra（只有最後的「另一種做法」用到）：NTUCPC Guide〈最短路徑〉、AP325 7.4.1（教材 PDF 第 248～252 頁）。

簡潔題意

\(n \times n\) 的方格，每格有高度，相鄰兩格高度差的絕對值是那一段步道的坡度。從左上角走到右下角（只能上下左右），先讓路上最陡的一段越小越好，在最陡一段最小的前提下再讓步數最少。印出最小坡度與最短長度（\(2 \le n \le 300\)，高度 \(\le 10^6\)）。

依正確通過的測試資料筆數給分，其中：

  • 子題組 1（\(20\) 分）：\(n \le 10\)，高度 \(\le 10\)。
  • 子題組 2（\(20\) 分）：高度 \(\le 100\)。
  • 子題組 3（\(60\) 分）：無額外限制。

先拿下 40 分：坡度從 0 往上試，每個坡度 BFS 一次

坡度上限 \(S\) 給定時，「坡度 \(> S\) 的那一段不能走」——方格圖上只留坡度 \(\le S\) 的邊，從入口 BFS，走不走得到出口、走得到的話最少幾步，一次 BFS 都有了。答案的坡度不會超過最大高度：高度 \(\le 100\) 時從 \(0\) 往上一個一個試，第一個走得到的就是最小坡度，那次 BFS 的步數就是最短長度。

#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<int>> h;
const int dr[4] = {-1, 1, 0, 0};                     // 上、下、左、右
const int dc[4] = {0, 0, -1, 1};

// 只走坡度 <= limit 的步道，回傳入口到出口的最短長度；走不到回傳 -1
int shortestUnder(int limit) {
    vector<vector<int>> dist(n, vector<int>(n, -1)); // -1＝還沒走到
    queue<pair<int, int>> q;
    dist[0][0] = 0;
    q.push({0, 0});
    while (!q.empty()) {
        int r = q.front().first, c = q.front().second;
        q.pop();
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
            if (dist[nr][nc] != -1) continue;        // 已經走到過：BFS 第一次到就是最短
            if (abs(h[r][c] - h[nr][nc]) > limit) continue;   // 這一段太陡，不能走
            dist[nr][nc] = dist[r][c] + 1;
            q.push({nr, nc});
        }
    }
    return dist[n - 1][n - 1];
}

int main() {
    cin >> n;
    h.assign(n, vector<int>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) cin >> h[i][j];
    for (int slope = 0; ; slope++) {                 // 坡度從 0 往上試，第一個走得到的就是答案
        int length = shortestUnder(slope);
        if (length != -1) {
            cout << slope << '\n' << length << '\n';
            break;
        }
    }
    return 0;
}

每次 BFS \(O(n^2)\)，最多 \(101\) 次，子題組 1、2 瞬間。高度到 \(10^6\) 就不行了：最壞要試 \(10^6\) 次，本站一筆答案坡度 \(470002\) 的測資跑超過 \(60\) 秒。

從 40 分到 100 分：對坡度二分搜

坡度 \(S\) 走得到，比 \(S\) 大的上限一定也走得到（能走的邊只會變多）；走不到，比 \(S\) 小的也走不到。「走不走得到」在坡度軸上只會從不行變成行一次，所以對坡度二分搜：在 \([0, 10^6]\) 裡找最小的走得到的坡度，約 \(20\) 次 BFS，最後再用這個坡度 BFS 一次拿最短長度。圖 1 是範例 2：坡度 \(\le 2\) 走不到、\(\le 3\) 走得到且最短 \(10\) 步。

圖 1：範例 2 的 6×6 方格，只走坡度不超過 2 的邊到不了出口；坡度不超過 3 時 BFS 最短 10 步

函式 shortestUnder 原封不動，主程式換成二分搜：

int main() {
    cin >> n;
    h.assign(n, vector<int>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) cin >> h[i][j];
    int lo = 0, hi = 1000000;                        // 答案一定在 [0, 10^6]：高度差最多就這麼大
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (shortestUnder(mid) != -1) hi = mid;      // 坡度 mid 走得到：答案 <= mid
        else lo = mid + 1;                           // 走不到：答案 > mid
    }
    cout << lo << '\n' << shortestUnder(lo) << '\n'; // 最後再用答案的坡度跑一次，拿最短長度
    return 0;
}

\(21\) 次 BFS、每次 \(9 \times 10^4\) 格，\(n = 300\) 本站實測 \(0.06\) 秒。二分搜的下界要從 \(0\) 開始（全部等高時答案是 \(0\)）、上界 \(10^6\)（高度差最多就這麼大）。

另一種做法：把「最陡的一段最小」當成最短路（Dijkstra）

把每格當成節點、相鄰高度差當邊權，「一條路的代價＝路上最大的邊權」。這種代價也有最短路的性質：到某格最平緩的走法，它的前半段也一定是最平緩的。所以把 Dijkstra 裡的「距離相加」換成「取 max」，從入口跑一次，就得到到每一格最小的「最陡一段」；出口那格的值就是答案的坡度，再用 shortestUnder 跑一次 BFS 求長度。\(O(n^2 \log n)\)，不用二分搜。函式 shortestUnder 一樣原封不動：

int main() {
    cin >> n;
    h.assign(n, vector<int>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) cin >> h[i][j];
    // best[r][c]：從入口走到 (r, c)，路上「最陡那一段」最小能壓到多少
    vector<vector<int>> best(n, vector<int>(n, INT_MAX));
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    best[0][0] = 0;
    pq.push({0, 0, 0});                              // (目前最陡坡度, 列, 行)，坡度小的先出來
    while (!pq.empty()) {
        auto [slope, r, c] = pq.top();
        pq.pop();
        if (slope > best[r][c]) continue;            // 過期的紀錄：這格已經有更平緩的走法
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
            int next = max(slope, abs(h[r][c] - h[nr][nc]));   // Dijkstra 的「相加」換成「取 max」
            if (next < best[nr][nc]) {
                best[nr][nc] = next;
                pq.push({next, nr, nc});
            }
        }
    }
    int limit = best[n - 1][n - 1];
    cout << limit << '\n' << shortestUnder(limit) << '\n';
    return 0;
}

測過再交：範例沒有「坡度 0」和「必須往回走」

兩個範例蓋到了最短不是曼哈頓距離（範例 1 長 \(12\)）和要繞路。沒蓋到：全部等高（坡度 \(0\)）、高度差頂到 \(10^6\)、必須往左或往上走、「坡度總和最小」和「最陡一段最小」不一樣的局面、BFS 順序錯會算錯長度的局面、最大規模。

輸入 正確輸出 這一筆在測什麼
2 ／ 0 0 ／ 0 0 0 ／ 2 全部等高：答案坡度 \(0\)，二分搜下界從 \(1\) 開始會印 1
2 ／ 0 1000000 ／ 1000000 0 1000000 ／ 2 高度差頂到 \(10^6\)，上界要夠大
5 ／ 0 0 0 0 0 ／ 9 9 9 9 0 ／ 0 0 0 0 0 ／ 0 9 9 9 9 ／ 0 0 0 0 0 0 ／ 16 蛇形：坡度 \(0\) 的路要往左走；只往右、往下走會印 9／8，長度直接印 \(2(n-1)\) 會印 0／8
3 ／ 0 2 4 ／ 0 50 6 ／ 0 0 8 2 ／ 4 坡度總和最小的路（\(0 + 0 + 0 + 8\)）最陡一段是 \(8\)，不是答案：求總和最小會印 8／4
3 ／ 1 2 1 ／ 2 0 0 ／ 1 1 2 1 ／ 4 BFS 的佇列換成堆疊（DFS 順序）會先繞遠路、印 1／6
用程式造：\(n = 300\)，第 \(i\) 列全是 \(3000i\) 3000 ／ 598 最大規模；每往下一列坡度 \(3000\)

六筆都親眼看過正確，這題就穩了。

常犯錯誤
  • 長度直接印 \(2(n-1)\)：以為最短步道就是曼哈頓距離，範例 1 印 1／8；本站測資掛 \(3\) 筆。
  • 只允許往右、往下走（DP）：範例 1 印 2／8。
  • 求坡度總和最小的路：題目要的是最陡一段最小，範例 1 印 2／8；自測表第 4 列印 8／4。
  • 判斷「走不走得到」用 >= limit 擋邊：等於上限的那段也能走，範例 1 印 2／12、範例 2 印 4／10。
  • dist 陣列只開一次、每次 BFS 沒重設：第二次 BFS 起點早就走過、什麼都走不出去，又因為舊的 dist 還在而以為走得到，範例 1 印 0／8。
  • 坡度從 0 往上一個一個試：高度到 \(10^6\) 時本站一筆測資超過 \(60\) 秒。