Editorial for 蜜蜂觀察 (APCS 2024-01 中級)

簡潔題意

\(m \times n\) 的蜂巢，每格一個英文字母（大小寫算不同字元）。蜜蜂從左下角出發，依序執行 \(k\) 步；每步的方向是 \(0 \sim 5\)，題目的表格寫明了每個方向「列、欄各怎麼變」。會離開蜂巢的那一步就留在原地，但這一步仍算執行完成。輸出每一步之後所在格子的字母串起來的字串（長度剛好 \(k\)），以及其中不同字元的種類數（\(1 \le m, n \le 20\)、\(1 \le k \le 100\)、\(0 \le d_i \le 5\)）。

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

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

先拿下子題組 1（60 分）：蜂巢只有兩列，直接宣告兩個 string

\(m = 2\) 時蜂巢就是上、下兩列，一列剛好是一條字串——直接宣告兩個 string（10.7）up、down 各讀一列就好，不用任何二維的東西。

蜜蜂的位置用兩個整數記：r 是列（\(0\) 上列、\(1\) 下列）、c 是欄。輸入是由上到下列出每一列，所以「上一列」是 r 減一、左下角就是 r = 1、c = 0。六個方向照題目的表格逐條翻譯成 if / else if（上冊 3.5），每一步固定的節奏是先算出下一格、檢查、通過才移動（13.4）——不論有沒有移動成功，這一步都要把目前所在格的字母接到答案後面：r == 0 就取 up[c]，否則取 down[c]。

不同字元的種類數，用「這個字母在更前面出現過嗎」來數：對每個位置 \(i\)，回頭掃 \(0 \sim i - 1\)，都沒撞到相同字母才算一種新的（上冊 4.6 的巢狀迴圈；\(k \le 100\)，最多也就幾千次比較）。

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

int main() {
    int m, n, k;
    cin >> m >> n >> k;   // 子題組 1 保證 m = 2，但還是要照格式讀掉

    string up, down;      // 蜂巢只有兩列：上列、下列各一條字串
    cin >> up >> down;

    int r = 1;   // 0 = 上列、1 = 下列；一開始在左下角
    int c = 0;
    string path = "";

    for (int i = 0; i < k; i++) {
        int d;
        cin >> d;

        int nr = r;   // 先算「下一格」，先不動 r、c
        int nc = c;
        if (d == 0) {              // 右上：上一列、同一欄
            nr = r - 1;
        } else if (d == 1) {       // 右：同一列、下一欄
            nc = c + 1;
        } else if (d == 2) {       // 右下：下一列、下一欄
            nr = r + 1;
            nc = c + 1;
        } else if (d == 3) {       // 左下：下一列、同一欄
            nr = r + 1;
        } else if (d == 4) {       // 左：同一列、上一欄
            nc = c - 1;
        } else {                   // 左上：上一列、上一欄
            nr = r - 1;
            nc = c - 1;
        }

        if (0 <= nr && nr < 2 && 0 <= nc && nc < n) {   // 會出界就留在原地
            r = nr;
            c = nc;
        }
        if (r == 0) {
            path += up[c];
        } else {
            path += down[c];
        }
    }

    int distinct = 0;
    for (int i = 0; i < k; i++) {
        bool appeared = false;             // path[i] 這個字母在更前面出現過嗎？
        for (int j = 0; j < i; j++) {
            if (path[j] == path[i]) {
                appeared = true;
            }
        }
        if (!appeared) {
            distinct++;                    // 第一次出現才算一種
        }
    }

    cout << path << '\n';
    cout << distinct << '\n';
    return 0;
}

兩個地方別踩：

  • 「留在原地」的那一步還是要接一個字母——範例 1 的第 \(4\) 步就是撞牆留在 a，答案裡照樣有那個 a。
  • 六段翻譯完拿範例 1 對一次：Tyaau、4。

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

從 60 分到 100 分：六個方向也是一張表

列數不再固定是 \(2\)，只差三個地方要改：

① 兩條字串換成「字串的 vector」。vector<string> hive(m)，一列讀一條（13.1 的字元地圖），hive[r][c] 就是第 r 列第 c 欄的字母——子題版那段「r == 0 取 up、否則取 down」的 if 直接消失。

② 六段 if 換成方向表。「往方向 \(d\) 走一步，列和欄各加多少」是固定的六組數字，把題目的表格照抄成兩個陣列 dr、dc（13.3）：

\(d\) 移動方式 dr[d]（列） dc[d]（欄）
\(0\) 右上（上一列、同一欄） \(-1\) \(0\)
\(1\) 右（同一列、下一欄） \(0\) \(1\)
\(2\) 右下（下一列、下一欄） \(1\) \(1\)
\(3\) 左下（下一列、同一欄） \(1\) \(0\)
\(4\) 左（同一列、上一欄） \(0\) \(-1\)
\(5\) 左上（上一列、上一欄） \(-1\) \(-1\)

之後「往方向 d 走一步」永遠是同樣的兩行 nr = r + dr[d]、nc = c + dc[d]，六個方向全部通用。這題的方向編號和順序都是題目給的，照題目定義排表就好——只有自己選編號的題目才需要講究順時針排。

③ nr < 2 改成 nr < m。子題版把列數寫死了，改成一般版時最容易漏掉的就是這個數字（常犯錯誤第 6 條）。

順手把數種類的方式也換成打表：字元本身就是一個小整數（8.1），英文字母的編碼都在 \(128\) 以內，所以開一個 bool seen[128]、直接拿字元當索引（上冊 6.7 的計數陣列，索引＝字元、值＝出現過沒），每個字母第一次出現時 distinct++——這樣邊走邊數，不用回頭掃。子題版的巢狀迴圈不換也是滿分。

// APCS 2024-01 中級 P2 蜜蜂觀察：六個方向也是一張表
#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 方向 0~5 依題目定義：右上、右、右下、左下、左、左上（方向表放檔頭，資料與邏輯分開）
const int dr[6] = {-1, 0, 1, 1, 0, -1};
const int dc[6] = {0, 1, 1, 0, -1, -1};

int main() {
    int m, n, k;
    cin >> m >> n >> k;

    vector<string> hive(m);
    for (int i = 0; i < m; i++) cin >> hive[i];

    int r = m - 1;   // 一開始在左下角
    int c = 0;
    string path;
    bool seen[128] = {};   // 記錄哪些字母出現過（用字元當索引，也是打表）
    int distinct = 0;

    for (int i = 0; i < k; i++) {
        int d;
        cin >> d;
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (0 <= nr && nr < m && 0 <= nc && nc < n) {   // 會出界就留在原地
            r = nr;
            c = nc;
        }
        char ch = hive[r][c];
        path.push_back(ch);
        if (!seen[(int)ch]) {
            seen[(int)ch] = true;
            distinct++;
        }
    }

    cout << path << '\n';
    cout << distinct << '\n';
    return 0;
}

path.push_back(ch) 就是在字串尾端多接一個字元，跟子題版的 += 一樣（10.8）。每一步只做固定幾個動作、\(k \le 100\)，速度完全不是問題。

測過再交：範例沒讓蜜蜂撞過左右牆

兩個範例合起來，蜜蜂只撞過上、下牆（範例 1 第 \(4\) 步、範例 2 第 \(9\) 與 \(11\) 步），從來沒有撞過左、右牆；方向 \(4\)（左）在兩個範例裡一次都沒出現；同一個字母的大小寫也沒有同時走到過。這幾件事都得自己造小測資補上：

輸入 正確輸出 這一筆在測什麼
1 3 5 ／ abc ／ 1 1 4 4 4 bcbaa ／ 3 方向 \(4\) 與撞左牆（範例裡一次都沒出現）；\(m = 1\) 時上、下全是牆
2 2 5 ／ Ab ／ aB ／ 1 1 0 4 3 BBbAa ／ 4 撞右牆；同一字母的大小寫都走到——是 \(4\) 種不是 \(2\) 種
1 1 3 ／ z ／ 0 2 4 zzz ／ 1 每一步都撞牆：第一行仍要有 \(k\) 個字、種類數是 \(1\)
3 1 1 ／ a ／ b ／ c ／ 1 c ／ 1 起點是左下角：往右撞牆留在 c；從左上角出發的程式會印 a
2 3 3 ／ xyz ／ uvw ／ 1 2 5 vvx ／ 2 斜向出界時只有一個座標出界（右下時列出界、欄沒有）：列、欄兩個都要查

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

常犯錯誤
  • 起點放在左上角（r = 0）：範例 1 照樣全對——它第一步就往右上撞牆、留在左上角的 T，之後的路徑跟從左下角出發一模一樣；範例 2 才現形（印 rMMmnnennii）。自測表第 4 列是手算得動的最小反例。
  • 出界只檢查列、忘了檢查欄：兩個範例都沒撞過左右牆，所以全過；一撞左牆 c 就變成 \(-1\)、讀到字串外面去。自測表第 1、2 列專門堵它。
  • 大小寫當成同一種字元：兩個範例的路徑裡都沒有同時出現同一字母的大小寫，一樣全過；自測表第 2 列會印 2（該印 4）。
  • 方向表抄錯——用六角格的直覺猜座標，例如把右上寫成「上一列、下一欄」：範例 1 印 yuBBB。表格照題目一格一格抄，抄完先對範例 1。
  • 第一行的長度不是 \(k\)：把起點的字母也接進去，範例 1 印 ATyaau；撞牆那一步沒接字母，印 Tyau；撞牆就直接結束，印 Tya。每一步（含留在原地的）都恰好接一個字母。
  • 從子題版改成完整版時 nr < 2 忘了改成 nr < m：範例 1（\(m = 2\)）照樣全對、\(60\) 分照拿；範例 2 的起點在第四列，之後每一步的 nr 都不小於 \(2\)、全被當成出界，蜜蜂永遠困在原地印 HHHHHHHHHHH。