想像你是一位在「數位山脈」中工作的測量員。你手上有一張高度圖 （heightmap）：一個 2D 的整數格子，每個數值代表該座標的海拔高度。 地圖裡藏著一個黃金山頂（golden peak）——全地圖的最高點。 你的任務是寫出一系列演算法，讓程式自己「爬」上這座山： 從一個格子移動到另一個格子、分析周圍的坡度來判斷哪個方向是上坡， 最後還要最佳化路線，用最少的步數登頂。

本教材對應課程 Lab 3 的三個活動，完成後你將學會：

• 撰寫非平凡的陣列程式：宣告、初始化、巡訪 2D 陣列， 並安全地處理邊界。

• 使用列舉（enumeration，enum）： 用型別安全的方式表達「方向」這種有限的選項。

• 培養搜尋演算法的直覺：從一步一步的貪婪爬坡， 進化到對數時間的二分搜尋。

• 用前置條件、後置條件與 assert 寫出 「自我檢查」的程式，並做到完整的分支覆蓋測試。

背景知識 A：二維陣列

從一維到二維：陣列的陣列

一維陣列 int[] 是「一排整數」。那要怎麼表示一張表格 （例如高度圖）呢？Java 的答案很直接： 把「每一列」做成一個一維陣列，再用另一個陣列把所有列裝起來。 所以 int[][] 讀作「int 陣列 的 陣列」。

// 建立一張 24 列（rows）高、12 行（columns）寬的格子
int[][] heightmap = new int[24][12];

有一點容易混淆：new int[24][12] 其實是 「24 個 int[12]」——24 列，每列 12 個整數。 Java 把維度寫成這個順序，是為了跟索引的寫法一致（見下文）。

直接初始化：巢狀大括號

從 Mountain Lab 產生器複製地圖資料時，數值會包在巢狀大括號裡； 每一組內層大括號就是一個「水平的列」：

int[][] smallMap = {
    {10, 20, 10},   // Row 0（第 0 列）
    {20, 50, 20},   // Row 1（第 1 列）
    {10, 20, 10}    // Row 2（第 2 列）
};

存取資料：map[row][column]

要讀取某一格的高度，用兩組方括號：map[row][column]。

• 第一個數字是垂直位置：你在哪一列（row）。

• 第二個數字是水平位置：你在哪一行（column）。

用 y 與 x 思考：方向與鄰居

在高度圖上導航時，我們習慣把兩個索引取名為 y 與 x：

• 列（y）：改變第一個索引，就是往北或南移動。

• 行（x）：改變第二個索引，就是往東或西移動。

站在 [y][x] 這一格想「看看四周」時，只要調整索引：

巡訪整張地圖：巢狀迴圈

處理 2D 陣列的標準寫法是「迴圈中的迴圈」——外層走過每一列， 內層走過該列的每一行：

for (int y = 0; y < map.length; y++) {          // 每一列
    for (int x = 0; x < map[0].length; x++) {   // 該列的每一行
        System.out.print(map[y][x] + " ");
    }
    System.out.println();   // 換列時順便換行
}

背景知識 B：列舉（enum）

為什麼需要 enum？

「方向」只有五種合法值：北、東、南、西、山頂。 如果用整數表示（0 代表北、1 代表東……），會有兩個大問題：

1. 沒有型別保護：int dir = 7; 完全合法， 但 7 是什麼方向？程式進入無意義的狀態，編譯器卻不會阻止你。

2. 可讀性差：看到 if (dir == 2)， 你得去翻文件才知道 2 是南還是西。

enum（enumeration，列舉）一次解決兩個問題： 它宣告一個新型別，而且這個型別只有你列出的那幾個值。

本 Lab 的 Direction 列舉

課程儲存庫已提供 Direction.java（不可修改）， 內容等價於：

public enum Direction {
    NORTH,   // 北：往上一列（y - 1）
    EAST,    // 東：往右一行（x + 1）
    SOUTH,   // 南：往下一列（y + 1）
    WEST,    // 西：往左一行（x - 1）
    PEAK     // 山頂：目前格子比四個鄰居都高
}

每個列舉值（如 Direction.NORTH）都是 Direction 型別的唯一物件，所以可以放心用 == 比較：

Direction dir = lookAround(y, x, heightmap);
if (dir == Direction.PEAK) {
    System.out.println("登頂成功！");
}

只要你的 Java 檔跟 Direction.java 放在同一個資料夾， 就能直接使用這個型別，不需要（也不應該）自己重新定義。

enum 與 switch 是天生一對

根據方向決定「怎麼移動」時，switch 比一長串 if-else 清楚得多。Java 14 之後更推薦箭頭 switch：

// 傳統寫法：每個 case 要自己 break，
// 忘了就會「掉落」到下一個 case（fall-through）——經典 bug！
switch (dir) {
    case NORTH:
        y--;
        break;      // 沒寫 break 的話會繼續執行 case EAST！
    case EAST:
        x++;
        break;
    // ...
}

// 箭頭寫法（Java 14+）：每個分支獨立，不會掉落，推薦！
switch (dir) {
    case NORTH -> y--;   // 北：列索引減 1（往上）
    case EAST  -> x++;   // 東：行索引加 1（往右）
    case SOUTH -> y++;   // 南：列索引加 1（往下）
    case WEST  -> x--;   // 西：行索引減 1（往左）
    case PEAK  -> { }    // 什麼都不做
}

背景知識 C：契約式思考——前置條件、後置條件與 assert

函式是一份契約

一個設計良好的函式，就像一份契約（contract）：

• 前置條件（precondition）：呼叫者必須保證的事。 「你給我的參數必須長這樣，否則後果自負。」

• 後置條件（postcondition）：函式必須保證的事。 「只要你遵守前置條件，我保證回傳值一定滿足這些性質。」

例如 lookAround(y, x, heightmap) 的契約可以這樣寫：

用 assert 把契約寫進程式裡

Java 的 assert 語句讓契約「活」起來——條件不成立就立刻停下來：

assert 條件;                 // 條件為 false 時拋出 AssertionError
assert 條件 : "錯誤訊息";     // 加上說明訊息，除錯更快

boolean assertionsEnabled = false;
assert assertionsEnabled = true;   // 有開啟才會執行這個賦值
if (!assertionsEnabled) {
    System.out.println("【警告】assert 未啟用！請改用：java -ea Mountain");
}

問題設定：高度圖與黃金山頂

規則整理

把講義的設定翻成精確的規格：

• 高度圖是 \(m \times n\) 的 2D 整數陣列； heightmap[y][x] 是座標 \((y, x)\) 的海拔。

• 地圖上有唯一的最高點（黃金山頂）。

• Mountain Lab 產生的地圖保證：局部最佳就是全域最佳 ——在任何一格往「最高的鄰居」走，都會嚴格更接近山頂。 （這個保證是 climb 與 fastTravel 正確性的基石！）

• 地圖邊界之外的高度視為 0 或某個非常低的數字。

邊界處理的核心技巧：heightAt

「山頂在角落」時，某些鄰居根本不存在；直接讀 map[-1][0] 會當掉。與其在主邏輯裡寫四段重複的邊界判斷， 不如把「安全讀取」包成一個小函式——這就是抽象化的威力：

/** 「界外」的高度值：選 int 的最小值，約 -21 億。 */
static final int OUT_OF_BOUNDS = Integer.MIN_VALUE;

/** 安全讀取 (y, x) 的高度；越界時回傳 OUT_OF_BOUNDS。 */
static int heightAt(int y, int x, int[][] heightmap) {
    boolean insideRows = 0 <= y && y < heightmap.length;
    boolean insideCols = 0 <= x && x < heightmap[0].length;
    if (!insideRows || !insideCols) {
        return OUT_OF_BOUNDS;   // 界外：回傳「超級低」的高度
    }
    return heightmap[y][x];     // 界內：正常讀取
}

Activity 1：lookAround——觀察四周

規格

Direction lookAround(int y, int x, int[][] heightmap)

比較 \((y, x)\) 與北、南、東、西四個鄰居的高度，回傳 最高鄰居所在的方向 （NORTH / EAST / SOUTH / WEST）； 若目前格子比所有鄰居都高，回傳 PEAK。

逐步推導

整個函式其實只有四個步驟：

1. 檢查前置條件：地圖是非空矩形、\((y,x)\) 在圖內。

2. 讀取五個高度：自己一個、鄰居四個 ——用 heightAt，邊界自動安全。

3. 找出四鄰的最大值：Math.max 一次比兩個， 巢狀呼叫三次就能比出四個值的最大。

4. 判斷：自己比最大鄰居還高 \(\Rightarrow\) PEAK； 否則回傳最大鄰居的方向。

static Direction lookAround(int y, int x, int[][] heightmap) {
    // ---- 前置條件檢查（執行時要加 -ea 才會生效）----
    assert isRectangular(heightmap)
            : "前置條件違反：heightmap 必須是非空的矩形陣列";
    assert 0 <= y && y < heightmap.length
            : "前置條件違反：y=" + y + " 超出列範圍";
    assert 0 <= x && x < heightmap[0].length
            : "前置條件違反：x=" + x + " 超出行範圍";

    // ---- 讀取自己與四個鄰居的高度 ----
    int current = heightmap[y][x];                 // 腳下的高度
    int north   = heightAt(y - 1, x, heightmap);   // 北：上一列
    int east    = heightAt(y, x + 1, heightmap);   // 東：右一行
    int south   = heightAt(y + 1, x, heightmap);   // 南：下一列
    int west    = heightAt(y, x - 1, heightmap);   // 西：左一行

    // ---- 找出四個鄰居中的最大高度 ----
    int best = Math.max(Math.max(north, east), Math.max(south, west));

    // ---- 判斷結果 ----
    if (current > best) {
        return Direction.PEAK;      // 我比所有鄰居都高：山頂！
    }
    // 依「北 → 東 → 南 → 西」的優先順序，回傳第一個最高的鄰居
    if (north == best) return Direction.NORTH;
    if (east == best)  return Direction.EAST;
    if (south == best) return Direction.SOUTH;
    return Direction.WEST;          // 剩下的只可能是西
}

兩個值得注意的設計決定

（一）「嚴格更高」才算山頂。 判斷式是 current > best 而不是 >=。 若自己跟最高鄰居一樣高，我們選擇回傳那個鄰居的方向， 而不是宣稱自己是山頂——因為山頂的定義是「比鄰居都高」。

（二）打平（tie）時行為要明確。 若兩個鄰居同為最高（例如講義 \(3\times3\) 地圖的角落， 東、南同為 20），程式依「北 \(\to\) 東 \(\to\) 南 \(\to\) 西」 的順序取第一個。Mountain Lab 的有效地圖沿途不會出現這種情況， 但讓程式行為明確且可預測永遠是好習慣—— 這也讓我們的測試可以放心斷言結果。

測試策略

Activity 2：climb——一步一步爬到山頂

貪婪爬坡法

int[] climb(int[][] heightmap)

策略非常直觀，叫做貪婪爬坡法（greedy hill climbing）：

1. 站在 [0][0]。

2. lookAround 看看四周。

3. 是 PEAK？結束！否則往回報的方向走一步，回到步驟 2。

「貪婪」的意思是：每一步只看眼前哪邊最高就往哪邊走， 從不回頭、也不做長遠規劃。一般的地形上貪婪法可能被 「假山頂」（局部最高點）騙住；但 Mountain Lab 的地圖保證 局部最佳就是全域最佳，所以貪婪法在這裡必定成功。

完整實作

static int[] climb(int[][] heightmap) {
    assert isRectangular(heightmap)
            : "前置條件違反：heightmap 必須是非空的矩形陣列";

    int y = 0;          // 目前位置：從左上角 [0][0] 出發
    int x = 0;
    int steps = 0;      // 已經走了幾步

    Direction dir = lookAround(y, x, heightmap);
    while (dir != Direction.PEAK) {       // 還不是山頂就繼續走
        switch (dir) {                    // 依方向更新座標
            case NORTH -> y--;            // 北：往上一列
            case EAST  -> x++;            // 東：往右一行
            case SOUTH -> y++;            // 南：往下一列
            case WEST  -> x--;            // 西：往左一行
            case PEAK  -> { }             // 不可能（while 已排除）
        }
        steps++;

        // 防禦性檢查：步數絕不可能超過格子總數
        assert steps <= heightmap.length * heightmap[0].length
                : "步數超過格子總數：這張地圖大概不是有效的單峰地圖";

        dir = lookAround(y, x, heightmap);   // 到新位置再看一次
    }

    // 依講義要求：印出總步數
    System.out.println("'climb' found the peak in " + steps + " steps!");

    // 後置條件：回傳的座標必須真的是山頂
    assert lookAround(y, x, heightmap) == Direction.PEAK
            : "後置條件違反：climb 停下來的位置不是山頂";

    return new int[]{y, x};   // 打包成長度 2 的新陣列 {y, x}
}

幾個細節值得留意：

• 回傳值是「新建的長度 2 陣列」 new int[]{y, x}——先 \(y\) 後 \(x\)， 跟索引順序一致。

• 步數訊息的格式依講義： ’climb’ found the peak in 39 steps!。

• 山頂如果就在起點（[0][0] 本身最高）， 迴圈一次都不會執行，印出 0 步——這是重要的邊界情況。

Activity 3：fastTravel——矩形二分搜尋

動機：climb 太慢了

climb 可靠但緩慢：\(m \times n\) 的地圖上，最壞要走 \((m-1) + (n-1)\) 步（起點在一角、山頂在對角）。 \(1024 \times 1024\) 的地圖就是最多 2046 步。 能不能不要一格一格走，而是「跳」著找？

回想一維二分搜尋：在排好序的陣列裡找目標時， 每次探測中間元素，就能丟掉一半的搜尋範圍。 關鍵在於：中間元素的資訊告訴我們「目標一定不在哪半邊」。

把二分搜尋升級到 2D

在高度圖上，lookAround 就扮演這個「指路」的角色。 我們隨時維護一個搜尋矩形 \([\texttt{top} .. \texttt{bottom}] \times [\texttt{left} .. \texttt{right}]\)， 並維持一個迴圈不變量（loop invariant）： 山頂一定在矩形裡。每一輪：

1. 取矩形中心點 \((\texttt{midY}, \texttt{midX})\)， 呼叫 lookAround。

2. 回傳 PEAK \(\Rightarrow\) 找到了，結束。

3. 否則依方向砍掉一半：

完整實作

static int[] fastTravel(int[][] heightmap) {
    assert isRectangular(heightmap)
            : "前置條件違反：heightmap 必須是非空的矩形陣列";

    // 搜尋範圍：一開始是整張地圖（都是「含」邊界的索引）
    int top    = 0;
    int bottom = heightmap.length - 1;
    int left   = 0;
    int right  = heightmap[0].length - 1;

    int steps = 0;   // 探測（probe）了幾次

    while (true) {
        // 取搜尋矩形的中心點（整數除法自動向下取整）
        int midY = (top + bottom) / 2;
        int midX = (left + right) / 2;

        steps++;
        Direction dir = lookAround(midY, midX, heightmap);

        if (dir == Direction.PEAK) {
            System.out.println(
                    "'fastTravel' found the peak in " + steps + " steps!");
            return new int[]{midY, midX};
        }

        // 根據方向，砍掉「山頂不可能在」的那半邊
        switch (dir) {
            case NORTH -> bottom = midY - 1;  // 山頂在更北：往上縮
            case SOUTH -> top    = midY + 1;  // 山頂在更南：往下縮
            case EAST  -> left   = midX + 1;  // 山頂在更東：往右縮
            case WEST  -> right  = midX - 1;  // 山頂在更西：往左縮
            case PEAK  -> { }                 // 不可能（上面已 return）
        }

        // 迴圈不變量：山頂永遠在 [top..bottom] x [left..right] 裡
        assert top <= bottom && left <= right
                : "搜尋矩形變成空的：這張地圖大概不是有效的單峰地圖";
    }
}

效能比較

表中 \(24\times12\) 與 \(128\times128\) 兩列是隨附程式的實測結果 （見下一節的執行輸出）。地圖越大，差距越驚人—— 這就是對數時間演算法的威力。

測試工程：錐形地圖與窮舉驗證

手寫測試地圖很快就會遇到瓶頸：想測「山頂在任何位置都正確」， 總不能手刻幾百張地圖。隨附程式用了一個小小的測試工程技巧 ——寫一個地圖產生器，再配一個理論答案公式：

/** 以 (peakY, peakX) 為山頂的「錐形」地圖：高度隨距離遞減。 */
static int[][] coneMap(int rows, int cols, int peakY, int peakX) {
    int[][] map = new int[rows][cols];
    int base = 3 * rows + 2 * cols;   // 讓所有高度都是正數
    for (int y = 0; y < rows; y++) {
        for (int x = 0; x < cols; x++) {
            map[y][x] = base - 3 * Math.abs(y - peakY)
                             - 2 * Math.abs(x - peakX);
        }
    }
    return map;
}

兩個方向的權重故意取不同值（3 與 2）， 這樣四個鄰居永遠不會同高、每一格的正確答案唯一，而且有封閉公式： 列還沒對齊山頂時答案必是 NORTH/SOUTH （權重 3 壓過 2），列對齊後看東西，兩者都對齊就是 PEAK。 於是可以窮舉——每種地圖尺寸 \(\times\) 每個山頂位置 \(\times\) 每個座標——逐一比對 lookAround 的輸出， 一口氣驗證 87,667 筆。 同一批地圖也拿來系統化測試 climb （斷言步數恰等於曼哈頓距離）與 fastTravel （斷言探測數不超過理論上限）。

實際執行 java -ea Mountain 的輸出節錄：

=== Lab 3: Mountain Climbing — 完整測試 ===
[1] lookAround：3x3 講義範例地圖 ... 通過
[2] lookAround：3x4 地圖 12 格全驗證（分支覆蓋）... 通過
[3] lookAround：1x1／單列／單行 退化地圖 ... 通過
[4] lookAround：錐形地圖窮舉測試，共比對 87667 個座標 ... 通過
[5] climb：手工地圖測試
'climb' found the peak in 0 steps!
'climb' found the peak in 4 steps!
    ...
    地圖 24x12，山頂在 (23,11)：
      'climb' found the peak in 34 steps!
      'fastTravel' found the peak in 8 steps!
    ...
[7] 步數比較：128x128 地圖，山頂在 (100, 111)
    'climb' found the peak in 211 steps!
    'fastTravel' found the peak in 9 steps!
    同一座山，climb 走了 211 步；fastTravel 只探測 9 次！

=== 全部測試通過！ ===

編譯、執行與繳交

編譯與執行

把 Direction.java 與 Mountain.java 放在同一個資料夾，然後：

$ javac Direction.java Mountain.java   # 編譯（產生 .class 檔）
$ java -ea Mountain                    # 執行，-ea 開啟 assert

用 git 繳交

依照講義，完成後記得 add、commit、push：

$ git add Mountain.java                    # 或你的檔案名稱
$ git commit -m "Completed mountain lab"
$ git push

離開實驗課之前，確認你已經跟助教討論過你的程式， 而且所有工作都已經 commit 並 push 到 GitLab！

延伸挑戰

以下挑戰不在 Lab 要求範圍內，但能大幅加深理解：

1. 流向圖產生器：寫 printFlowMap(int[][] heightmap)， 每格印出一個字元（^、>、v、 <、P）代表 lookAround 的結果， 重現圖 3 的效果。

2. 記錄完整路徑：讓 climb 除了山頂座標外， 也記下沿途經過的每個座標（提示：使用 ArrayList<int[]>，在 java.util 套件裡）。

3. 高原問題：手工造一張含相鄰同高格子的地圖， 觀察 climb 的防禦性 assert 如何避免無窮迴圈。 想想：如果把 lookAround 的判斷改成 「不嚴格更高就算 PEAK」，會有什麼新問題？

4. 多峰地圖：造一張有兩個局部高點的地圖。 climb 會發生什麼事？fastTravel 呢？ 哪一個的錯誤比較「安靜」（不容易被發現）？

5. 證明步數上限：解釋為什麼 fastTravel 的探測次數不超過 \(\lceil\log_2 m\rceil + \lceil\log_2 n\rceil + 1\)。 （提示：每次非 PEAK 探測， 某一個維度的範圍長度至少減半。）

6. 八方向擴充：若允許斜走（東北、西北……）， Direction 的五個值就不夠用了。 在不修改 Direction.java 的前提下， 設計你自己的 Direction8 列舉並改寫三個函式。

完整程式碼：Direction.java

完整程式碼：Mountain.java