Editorial for 蒐集寶石 (APCS 2024-10 中級)

簡潔題意

一個 \(M \times N\) 的場地（橫列、直行都從 \(0\) 開始編號），格子上的數字是寶石數，\(-1\) 是牆，場地四周視為牆。機器人從 \((r, c)\) 出發、面向東（右），照下面的規則走：

  1. 走到的格子沒有寶石就停止；否則
  2. 得分加上這一格目前的寶石數，並拿走一顆寶石；
  3. 總得分是 \(K\) 的倍數就右轉；
  4. 前方是牆或界外就右轉，一直轉到前方走得進去為止；
  5. 走進前方的格子，回到規則 1。

輸出機器人拿到的寶石數——注意不是得分（\(1 \le M \le 100\)、\(2 \le N \le 100\)、\(2 \le K \le 20\)、每格寶石 \(0\) 到 \(K - 1\) 顆，保證起點不是牆、機器人一定會停）。

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

  • 子題組 1（\(60\) 分）：\(M = 1\)。
  • 子題組 2（\(40\) 分）：無額外限制。

先拿下子題組 1（60 分）：場地只有一列

\(M = 1\) 時整個場地就是一橫排，機器人只可能往東或往西走。「右轉」呢？往南、往北都是界外，所以右轉一次之後，規則 4 一定會讓它繼續轉——在一列上，右轉的結果必然是迴轉（題目的評分說明自己就提示了這件事）。

所以方向不用記東南西北，用一個 step 就夠：+1 是往東、-1 是往西，迴轉就是 step = -step。

#include <iostream>
using namespace std;

const int MAX_N = 100;

int main() {
    int M, N, K, r, c;
    cin >> M >> N >> K >> r >> c;   // 子題組 1 保證 M = 1，r 一定是 0，但還是要讀掉

    int gem[MAX_N];
    for (int j = 0; j < N; j++) {
        cin >> gem[j];   // -1 是牆，其餘是寶石數
    }

    int step = 1;    // +1 = 往東（右）、-1 = 往西（左）
    int score = 0;   // 總得分
    int gems = 0;    // 拿到的寶石數（答案）

    while (gem[c] != 0) {          // 規則 1：這一格沒寶石就停止
        score += gem[c];           // 規則 2：得分加上這一格目前的寶石數，
        gem[c] -= 1;               //         並拿走一顆
        gems += 1;

        if (score % K == 0) {      // 規則 3：得分是 K 的倍數就右轉——一列上右轉＝迴轉
            step = -step;
        }

        while (c + step < 0 || c + step >= N || gem[c + step] == -1) {
            step = -step;          // 規則 4：前方出界或是牆，就迴轉
        }

        c += step;                 // 規則 5：走進前方的格子
    }

    cout << gems << endl;
    return 0;
}

兩個地方別踩：

  • 寶石數是 \(0\) 的格子不是牆——機器人走得進去，走進去之後才因為規則 1 停止。擋路的只有 -1 和界外。
  • 主迴圈的五段註解就是題目的規則 1 到 5，一條對一條——模擬題照著規則的順序寫，最不容易漏。

這份程式交上去，範例 2 和子題組 2 會 WA——這是正常的，逐筆給分之下子題組 1 的 \(60\) 分穩穩到手。

從 60 分到 100 分：方向陣列

完整版的場地是二維的，方向變成東南西北四種。這題唯一要學的新招就是方向陣列：把四個方向照「右轉一次」的順序排好——東、南、西、北——右轉就變成一行

dir = (dir + 1) % 4;

轉四次剛好繞一圈回到東（% 見上冊 2.6）。規則 3 和規則 4 共用這一行，不用寫四個方向的 if。

跟子題組 1 的程式比，只差兩個地方：step 換成 dir＋方向陣列，一維陣列換成二維（上冊 6.9）。會不會太慢？每繞一圈迴圈就拿走一顆寶石，場上最多 \(100 \times 100 \times 19 = 190000\) 顆，所以最多也就這麼多輪——離危險區還遠得很（估算方法見上冊 4.9）。順帶一提，這也是「模擬一定會結束」的理由：寶石有限，每一步都在消耗它。

#include <iostream>
using namespace std;

const int MAX_SIZE = 100;

// 方向照「右轉一次」的順序排：東 → 南 → 西 → 北
// 右轉就是 dir 加 1（繞一圈回到東）
const int dr[4] = {0, 1, 0, -1};
const int dc[4] = {1, 0, -1, 0};

int main() {
    int M, N, K, r, c;
    cin >> M >> N >> K >> r >> c;

    int grid[MAX_SIZE][MAX_SIZE];
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            cin >> grid[i][j];   // -1 是牆，其餘是寶石數
        }
    }

    int dir = 0;     // 0 = 東、1 = 南、2 = 西、3 = 北
    int score = 0;   // 總得分
    int gems = 0;    // 拿到的寶石數（答案）

    while (grid[r][c] != 0) {      // 規則 1：這一格沒寶石就停止
        score += grid[r][c];       // 規則 2：得分加上這一格目前的寶石數，
        grid[r][c] -= 1;           //         並拿走一顆
        gems += 1;

        if (score % K == 0) {      // 規則 3：得分是 K 的倍數就右轉
            dir = (dir + 1) % 4;
        }

        while (true) {             // 規則 4：前方出界或是牆，就一直右轉
            int nr = r + dr[dir];
            int nc = c + dc[dir];
            if (nr >= 0 && nr < M && nc >= 0 && nc < N && grid[nr][nc] != -1) {
                break;             // 前方走得進去，右轉到此為止
            }
            dir = (dir + 1) % 4;
        }

        r += dr[dir];              // 規則 5：走進前方的格子
        c += dc[dir];
    }

    cout << gems << endl;
    return 0;
}

幾個寫法上的細節：

  • dr 是列的變化、dc 是行的變化，兩個陣列要用同一套順序——排錯順序右轉會變成左轉，整支程式就歪了（常犯錯誤第 1 條）。
  • 規則 4 寫成 while (true) 加 break（上冊 4.5）：轉到前方走得進去才跳出。它不會轉不停——機器人是從某個格子走進來的，往回走的那個方向一定通。
  • 先算好 nr、nc 再檢查，檢查通過才真的移動——「看一步、走一步」分開寫，是所有地圖模擬題共用的骨架。

測過再交：範例沒考到的三種情況

兩個範例合起來，還有幾種情況沒出現過：起始格就是 \(0\) 顆（一開場就停止）、規則 3 轉完、規則 4 接著轉（範例 2 的連轉是純規則 4 造成的，跟得分無關）、以及得分和寶石數不同、小到手算得動的對照組。自己造小測資補上：

輸入 正確輸出 這一筆在測什麼
1 2 2 0 0 ／ 0 1 0 起始格就沒寶石：一顆都拿不到就停止
2 2 2 0 0 ／ 1 -1 ／ 1 1 2 在 \((1, 0)\) 得分湊到 \(2\)：規則 3 右轉朝西、出界，規則 4 接著轉朝北——兩條規則連動；方向排成逆時針的話這筆會印 3
1 2 3 0 0 ／ 2 1 3 答案是寶石數不是得分——這筆的得分是 \(4\)，印成 4 就是輸出錯欄位
1 3 20 0 0 ／ 1 1 0 2 \(0\) 顆的格子走得進去：一路向東走進 0 那格才停

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

常犯錯誤
  • 方向陣列排成逆時針（右轉變左轉）：這個錯特別陰險——一列上左轉也是迴轉，跟右轉沒有差別，所以範例 1 全對、子題組 1 的 \(60\) 分照拿，範例 2 才現形（印 6）。自測表第 2 列是手算得動的最小反例（印 3）。
  • 規則 4 只轉一次：右轉一次之後前方可能還是牆——範例 2 的機器人在 \((3, 3)\) 就得連轉兩次。只轉一次的程式會直接撞進牆裡，把牆的 \(-1\) 當寶石加進得分，範例 2 印 11。
  • 先判斷倍數才拿寶石（規則 2、3 順序顛倒）：判斷用到的是舊得分，轉向的時機全錯，範例 1 印 3。
  • 忘了把格子的寶石減一：寶石永遠拿不完、規則 1 永遠等不到 \(0\)，範例 1 直接跑不完（在 OJ 上就是 TLE）。
  • 輸出得分不是寶石數：範例 1 印 7（該印 5）。自測表第 3 列就是為它設計的。
  • 用「走的步數」當答案：題敘講範例時說「總步數加上起始位置的 \(1\) 顆」——直接數步數會少掉起始那一顆，範例 1 印 4，每一筆都恰好少 \(1\)。