機器人的路徑 (APCS 2019-06 中級) 題解

Editorial for 機器人的路徑 (APCS 2019-06 中級)

簡潔題意

\(n\) 列 \(m\) 行的地圖（\(1 \le n, m \le 100\)），每格一個整數（\(0 \le a_{r,c} < 1000000\)，所有數值互不相同）。機器人從全圖最小值的格子出發，每一步只看上、下、左、右四個鄰格，排除出界和已經走過的，剩下的候選格裡走到數值最小的那一格；沒有候選格就停。輸出走過的所有格子（含起點與終點）數值總和。

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

子題組 1（\(20\) 分）：\(n = 1\)。
子題組 2（\(20\) 分）：\(1 \le n, m \le 20\)。
子題組 3（\(60\) 分）：無額外限制。

先拿下子題組 1（20 分）：只有一列，候選格只有左右兩個

\(n = 1\) 時地圖就是一排 \(m\) 個數，一維陣列裝得下（上冊 6.1）。機器人的位置只要一個整數 pos，鄰格也只剩「左邊一格 pos - 1」和「右邊一格 pos + 1」。照題目規則逐條翻譯：

起點：讀入的時候順便找最小值在哪——打擂台（上冊 3.9），a[c] < a[pos] 就換人。讀完 pos 就是起點，馬上標記走過、計入總和。
候選格：左邊一格要「沒出界（pos - 1 >= 0）而且沒走過」，右邊一格同理。兩個候選格裡挑數值小的——用一個 bestValue 從最大值往下壓、next 記是哪一格；next 還是 \(-1\) 就代表左右都不能走，停止。
移動：走到 next、標記、加總，回到第 2 步。

「走過了沒」用一個 bool 陣列記（上冊 6.7），= {} 一開始全 false（上冊 6.5）。總和先用 long long：一列 \(100\) 格、每格不到 \(10^6\)，其實 int 還裝得下，但完整版會超過（下一段算給你看），不如一開始就用對的型態。

#include <iostream>
#include <climits>
using namespace std;

const int MAX_M = 100;

int main() {
    int n, m;
    cin >> n >> m;                 // 子題組 1 保證 n = 1：地圖只有一列
    int a[MAX_M];
    bool visited[MAX_M] = {};      // 走過了沒，一開始全 false
    int pos = 0;                   // 起點＝這一列最小值的位置
    for (int c = 0; c < m; c++) {
        cin >> a[c];
        if (a[c] < a[pos]) pos = c;
    }
    visited[pos] = true;
    long long answer = a[pos];

    while (true) {
        int next = -1;             // -1 代表「還沒找到候選格」
        int bestValue = INT_MAX;
        if (pos - 1 >= 0 && !visited[pos - 1] && a[pos - 1] < bestValue) {   // 左邊一格
            bestValue = a[pos - 1];
            next = pos - 1;
        }
        if (pos + 1 < m && !visited[pos + 1] && a[pos + 1] < bestValue) {    // 右邊一格
            bestValue = a[pos + 1];
            next = pos + 1;
        }
        if (next == -1) break;     // 左右都不能走：停止
        pos = next;
        visited[pos] = true;
        answer += a[pos];
    }
    cout << answer << '\n';
    return 0;
}

「還沒找到候選格」的記號用 \(-1\)，因為 \(-1\) 不可能是陣列索引；INT_MAX 住在 <climits>（上冊 2.3）。注意一列也會提早停：範例 1 剛好從最左邊一路走到底，但 2 1 3 4 這種排法，從 \(1\) 往左走到 \(2\) 之後左邊出界、右邊走過，機器人就停了——「一列就是全部加總」是錯的（自測表第 1 列）。

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

從 20 分到 100 分：四個鄰格打成表

地圖變成二維，改的只有「鄰格有幾個、怎麼算出來」：

地圖用巢狀 vector 讀（13.1），起點一樣是讀入時打擂台，只是要記 row、col 兩個座標。
四個鄰格不要寫四段 if——把「往第 \(d\) 個方向走一步，列和行各加多少」打成 dr[]、dc[] 兩個陣列（13.3），for (d = 0; d < 4; d++) 跑一圈就是枚舉四鄰格（13.6）。每個鄰格先判出界（13.2）、再判走過，都通過才跟 bestValue 比——跟一維版一模一樣的擂台，只是從兩個候選變成最多四個。
總和用 long long：最多 \(100 \times 100 = 10^4\) 格、每格不到 \(10^6\)，全走完可到 \(10^{10}\)，超過 int 的 \(2147483647\)（上冊 2.9）。子題組 2 的 \(20 \times 20\) 只有 \(4 \times 10^8\)、int 還夠——所以「只用 int」的程式小地圖全對、大地圖才出錯，很難靠範例發現。

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

// 四鄰格的方向表：上、下、左、右（只跑一圈、不轉向，所以不必順時針排）
const int dr[4] = {-1, 1, 0, 0};
const int dc[4] = {0, 0, -1, 1};

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m));
    int row = 0, col = 0;   // 起點＝全圖最小值的位置
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            cin >> grid[r][c];
            if (grid[r][c] < grid[row][col]) {
                row = r;
                col = c;
            }
        }
    }

    vector<vector<bool>> visited(n, vector<bool>(m, false));
    visited[row][col] = true;
    long long answer = grid[row][col];

    while (true) {
        int nextRow = -1, nextCol = -1;
        int bestValue = INT_MAX;
        for (int d = 0; d < 4; d++) {              // 枚舉四個鄰格
            int nr = row + dr[d];
            int nc = col + dc[d];
            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;   // 出界
            if (visited[nr][nc]) continue;                           // 走過
            if (grid[nr][nc] < bestValue) {
                bestValue = grid[nr][nc];
                nextRow = nr;
                nextCol = nc;
            }
        }
        if (nextRow == -1) break;                  // 沒有候選格：停止
        row = nextRow;
        col = nextCol;
        visited[row][col] = true;
        answer += grid[row][col];
    }

    cout << answer << '\n';
    return 0;
}

這題的方向表只需要「跑一圈」、不需要「右轉」，所以沒有照順時針排——表要怎麼排，看題目要不要轉向。visited 這張標記表和地圖同大小，走過就蓋章，候選格一律先看章（13.5）。速度不用擔心：每一步最多看四格、每格最多走一次，總共 \(4 \times 10^4\) 次上下。

測過再交：範例沒逼你在一列上停下來，也沒讓總和爆掉

範例 1 是一列、而且一路走到底；範例 2 有「停下來時還有格子沒走到」的情況，也有「走到比現在大的數字」（\(5 \to 8 \to 14\)）。沒測到的是：一列也會中途停、直的地圖、以及 int 裝不下的總和。

輸入	正確輸出	這一筆在測什麼
`1 4` ／ `2 1 3 4`	`3`	一列也會提早停：從 \(1\) 往左走到 \(2\)，左邊出界、右邊走過。「一列就是全部加總」的程式印 `10`，範例 1 抓不到
`1 1` ／ `0`	`0`	\(1 \times 1\)、數值 \(0\)：起點就是終點，四個方向全出界
`4 1` ／ `3` ／ `1` ／ `2` ／ `4`	`7`	直的地圖（範例 2 是橫的）：從 \(1\) 往下走 \(2\)、\(4\)，上面的 \(3\) 沒走到。出界判斷的 \(n\)、\(m\) 寫反的程式在這裡不是答錯就是讀到地圖外面
`100 100`，數值從 \(0\) 開始每格加 \(100\)、一列往右一列往左蛇形排（用程式產生）	`4999500000`	全圖走完、總和超過 `int`：答案用 `int` 的程式印 `704532704`，兩個範例都抓不到

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

常犯錯誤

每一步找全圖最小的沒走過格子（瞬間移動），或以為「反正會走完」直接全部加總：範例 1 剛好全走完所以過，範例 2 印 84（該印 62）；自測表第 1 列印 10。
把斜對角也當相鄰：範例 2 印 48。
沒有標記已走過：範例 1 就在 \(1\) 和 \(2\) 之間來回走不完（TLE）。
只肯走到比目前小的格子：題目要的是候選裡最小的，不必比現在小——範例 1 印 1。
答案用 int：兩個範例全過、子題組 2 也過；自測表第 4 列印 704532704。
出界判斷的 \(n\)、\(m\) 寫反（nr >= m、nc >= n）：範例 1 是 \(1 \times 7\)，出界的讀取馬上讓程式當掉；兩個都寫成 n 的版本範例 1 印 1。