骰子 (APCS 2020-07 中級) 題解

Editorial for 骰子 (APCS 2020-07 中級)

簡潔題意

\(n\) 顆骰子排成一列（位置 \(1 \sim n\)），初始方向全部一樣：上 \(1\)、下 \(6\)、前 \(4\)、後 \(3\)、右 \(2\)、左 \(5\)。依序做 \(m\) 次操作，每次給 \(a\)、\(b\)：\(b > 0\) 是交換目前位於位置 \(a\) 和位置 \(b\) 的兩顆骰子（整顆連方向一起換）；\(b = -1\) 是把位置 \(a\) 的骰子向前滾一次（新上＝舊後、新前＝舊上、新下＝舊前、新後＝舊下，左右不變）；\(b = -2\) 是向右滾一次（新上＝舊左、新右＝舊上、新下＝舊右、新左＝舊下，前後不變）。輸出最後每個位置骰子的頂面點數（\(1 \le n \le 20\)、\(1 \le m \le 100\)）。（APCS 逐筆給分。）

每顆骰子要記六個面，交換是整顆換

只記頂面不夠：向前滾之後的新頂面是「原本的後面」，向右滾是「原本的左面」——不知道其他面是什麼，下一次滾就算不出來。所以每顆骰子要記六個面的點數，初始值照題目抄；滾動就是「六個面之間搬家」，其中兩個面不動、四個面繞一圈。

還有兩件事題目寫得很清楚，照做就好：

交換是整顆換：位置 \(a\)、\(b\) 的骰子連方向一起對調，六個面都要換，不是只換頂面。
操作作用在「目前位置」：交換過之後，下一次對位置 \(a\) 的操作作用在剛換過來的那顆。只要我們一直用「位置」當索引、交換時把六個面一起換，這件事就自動對了。

兩個範例都沒有「同一顆骰子滾兩次」的情況——很多寫錯的程式範例照樣全過，後面自測表會補。下面給三種寫法：先照題目一句一句寫，再把規則打成表，最後用 vector 把它寫到最短。

寫法一：照題目四句話搬面

六個面各用一個陣列記：top[i]、bottom[i]……第 \(i\) 顆骰子住在索引 \(i\)（1-base 多開一格，上冊 6.3）。滾動是四個面繞一圈，寫成四句指派時要先把會被蓋掉的那一面存起來（上冊 3.9 交換兩數的暫存變數），再排成一條鏈：向前滾是「存舊上面 → 上←後 → 後←下 → 下←前 → 前←舊上」——每一步等號右邊的面都還沒被改過。順序排錯（例如照題目句子的順序 top = back; front = top;）第二句拿到的就是新的上面，整顆骰子亂掉。交換用 swap（上冊 7.6），六個陣列各換一次。

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

const int MAX_N = 20;

int main() {
    int n, m;
    cin >> n >> m;
    // 每顆骰子六個面，各用一個陣列記；第 i 顆骰子住在索引 i（1-base，多開一格）
    int top[MAX_N + 1], bottom[MAX_N + 1], front[MAX_N + 1], back[MAX_N + 1], left[MAX_N + 1], right[MAX_N + 1];
    for (int i = 1; i <= n; i++) {      // 初始方向照題目抄
        top[i] = 1;
        bottom[i] = 6;
        front[i] = 4;
        back[i] = 3;
        left[i] = 5;
        right[i] = 2;
    }
    for (int k = 0; k < m; k++) {
        int a, b;
        cin >> a >> b;
        if (b > 0) {                        // 交換兩顆骰子：六個面一起換
            swap(top[a], top[b]);
            swap(bottom[a], bottom[b]);
            swap(front[a], front[b]);
            swap(back[a], back[b]);
            swap(left[a], left[b]);
            swap(right[a], right[b]);
        } else if (b == -1) {               // 向前滾：先把會被蓋掉的上面存起來，再一面接一面搬
            int oldTop = top[a];
            top[a] = back[a];               // 新上面＝原本的後面
            back[a] = bottom[a];            // 新後面＝原本的下面
            bottom[a] = front[a];           // 新下面＝原本的前面
            front[a] = oldTop;              // 新前面＝原本的上面
        } else {                            // 向右滾：同樣先存上面
            int oldTop = top[a];
            top[a] = left[a];               // 新上面＝原本的左面
            left[a] = bottom[a];            // 新左面＝原本的下面
            bottom[a] = right[a];           // 新下面＝原本的右面
            right[a] = oldTop;              // 新右面＝原本的上面
        }
    }
    for (int i = 1; i <= n; i++) {
        if (i > 1) cout << ' ';
        cout << top[i];
    }
    cout << '\n';
    return 0;
}

寫法二：滾動規則打成表

題目裡有兩組固定不變的資料：初始六面，以及「新的每一面是原本的哪一面」這兩條規則——這種東西就該打成表（13.3 的方向表是同一招：照題目定義排表，程式只剩查表）。給六個面編號 \(0 \sim 5\)，一顆骰子就是一列六格 face[i][0..5]，全部骰子是一張 \(n \times 6\) 的二維陣列（上冊 6.9）。滾動規則寫成 rule[6]：新的第 \(f\) 面＝原本的第 rule[f] 面，題目那四句話一句一格、沒提到的面填自己。於是兩種滾動共用同一個 roll：先把這顆骰子的六面抄一份到 old，再 face[i][f] = old[rule[f]] 跑六格——暫存變數變成整份複本，順序問題跟著消失。陣列當參數傳進函式是上冊 7.7。

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

const int MAX_N = 20;
// 六個面的索引：0 上、1 下、2 前、3 後、4 左、5 右
const int TOP = 0, BOTTOM = 1, FRONT = 2, BACK = 3, LEFT = 4, RIGHT = 5;
// 初始骰子照題目抄：上 1、下 6、前 4、後 3、左 5、右 2
const int INITIAL[6] = {1, 6, 4, 3, 5, 2};
// 滾動規則打成表：新的第 f 面＝原本的第 rule[f] 面（題目那四句話一句一格，沒提到的面填自己）
const int FORWARD[6] = {BACK, FRONT, TOP, BOTTOM, LEFT, RIGHT};    // 新上＝舊後、新下＝舊前、新前＝舊上、新後＝舊下；左右不變
const int RIGHTWARD[6] = {LEFT, RIGHT, FRONT, BACK, BOTTOM, TOP};  // 新上＝舊左、新下＝舊右、前後不變；新左＝舊下、新右＝舊上

int face[MAX_N + 1][6];   // face[i][f]＝第 i 顆骰子的第 f 面

// 把第 i 顆骰子照 rule 滾一次
void roll(int i, const int rule[6]) {
    int old[6];
    for (int f = 0; f < 6; f++) old[f] = face[i][f];         // 先抄一份舊的
    for (int f = 0; f < 6; f++) face[i][f] = old[rule[f]];   // 新的第 f 面＝舊的第 rule[f] 面
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int f = 0; f < 6; f++) face[i][f] = INITIAL[f];
    }
    for (int k = 0; k < m; k++) {
        int a, b;
        cin >> a >> b;
        if (b > 0) {
            for (int f = 0; f < 6; f++) swap(face[a][f], face[b][f]);   // 交換兩顆骰子：六個面一起換
        } else if (b == -1) {
            roll(a, FORWARD);
        } else {
            roll(a, RIGHTWARD);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (i > 1) cout << ' ';
        cout << face[i][TOP];
    }
    cout << '\n';
    return 0;
}

跟寫法一比，換掉了三件事：六個平行陣列 → 一張 \(n \times 6\) 的表；兩段各四句的指派 → 兩張換位表＋一個迴圈；交換六個變數 → 迴圈換六格。兩種寫法答案完全一樣、都是滿分，不必急著換——寫法二的價值在題目變大的時候：多一種「向左滾」「向後滾」，寫法一要再各寫四句、順序再排一次，寫法二只是多抄一張表。

更簡潔的寫法：vector 讓整顆骰子一次交換、一次指派

寫法二還留著兩個迴圈：交換要六格各 swap 一次、滾動要先抄一份 old。這是 C 陣列的限制——陣列不能整個 a = b、也不能整個 swap（10.6 開頭說的那個遺憾）。把一顆骰子改成 vector<int>、全部骰子改成巢狀 vector（10.3），這兩件事都變成一句：

交換：swap(dice[a], dice[b])——兩顆骰子整個對調。
滾動：寫一個 rolled(die, rule) 回傳一顆新骰子（參數用 const vector<int>& 傳參考不複製，10.6），主程式 dice[a] = rolled(dice[a], FORWARD); 一句指派回去。函式裡讀的是傳進來的 die、寫的是新開的 result，「先抄一份 old」這件事自然消失——跟 13.7 讀舊表、寫新表是同一個道理。
初始化：vector<vector<int>> dice(n + 1, INITIAL)——\(n + 1\) 顆骰子，每一顆都是 INITIAL 的複本，連初始化的迴圈都省了。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 六個面的索引：0 上、1 下、2 前、3 後、4 左、5 右
const int TOP = 0, BOTTOM = 1, FRONT = 2, BACK = 3, LEFT = 4, RIGHT = 5;
const vector<int> INITIAL = {1, 6, 4, 3, 5, 2};                        // 初始骰子照題目抄
const vector<int> FORWARD = {BACK, FRONT, TOP, BOTTOM, LEFT, RIGHT};   // 新的第 f 面＝原本的第 rule[f] 面
const vector<int> RIGHTWARD = {LEFT, RIGHT, FRONT, BACK, BOTTOM, TOP};

// 回傳「die 照 rule 滾一次之後」的新骰子；die 本身沒被改，所以可以直接拿它查舊的面
vector<int> rolled(const vector<int>& die, const vector<int>& rule) {
    vector<int> result(6);
    for (int f = 0; f < 6; f++) result[f] = die[rule[f]];
    return result;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> dice(n + 1, INITIAL);   // n 顆骰子，每顆都是 INITIAL 的複本（索引 0 不用）
    for (int k = 0; k < m; k++) {
        int a, b;
        cin >> a >> b;
        if (b > 0) {
            swap(dice[a], dice[b]);                 // 整顆骰子一次交換
        } else if (b == -1) {
            dice[a] = rolled(dice[a], FORWARD);     // 整顆骰子一次指派：不必先抄一份 old
        } else {
            dice[a] = rolled(dice[a], RIGHTWARD);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (i > 1) cout << ' ';
        cout << dice[i][TOP];
    }
    cout << '\n';
    return 0;
}

三種寫法都是滿分；這一版最短，而且每一句都在講「一顆骰子」而不是「某一格」。（讀到下冊第十四單元之後還有第四種長相：六個面包成一個結構體，swap 和 = 同樣一句搞定。）

測過再交：兩個範例沒有同一顆骰子滾兩次

範例 1 是一顆骰子先右後前、範例 2 是三顆各滾一次再交換——沒有任何一顆骰子被滾第二次，也沒有「交換之後再去滾被換過來的那顆」。只記頂面、滾動時拿初始方向算、四句指派順序排錯、交換只換頂面、用骰子編號而不是位置來滾——這些錯兩個範例全過。自己補：

輸入	正確輸出	這一筆在測什麼
`1 4` ／ `1 -1` ×4	`1`	同一方向滾四次回到原狀：只記頂面或每次從初始方向算的程式印 `3`；四句指派沒先存舊上面的程式也印 `3`
`2 4` ／ `1 -1` ／ `1 -1` ／ `2 -2` ／ `2 -2`	`6 6`	同一顆連滾兩次：前滾兩次、右滾兩次頂面都變成原本的下面。照題目句子順序指派（`top = back; front = top;`）的程式印 `3 5`
`1 2` ／ `1 -1` ／ `1 -2`	`5`	先前後右（範例 1 是先右後前、答案 `3`）：滾動順序不同結果不同，兩個方向的程式都要各自對
`2 3` ／ `1 -2` ／ `1 2` ／ `2 -2`	`1 6`	交換之後再滾被換過來的那顆：只換頂面的程式印 `1 5`；用骰子編號而不是位置來滾的程式印 `5 5`

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

常犯錯誤

只記頂面（向前滾就把頂面設成 \(3\)、向右滾設成 \(5\)）：兩個範例全過；自測表第 1 列印 3。
四句指派沒先存舊上面（front = top 拿到的是剛改過的新上面）：兩個範例全過；自測表第 1 列印 3。
照題目句子的順序指派（top = back; front = top; bottom = front; back = bottom;）：後三句都在抄前一句剛寫進去的新值——兩個範例全過；自測表第 2 列印 3 5、第 4 列印 1 5。
交換只換頂面：兩個範例全過；自測表第 4 列印 1 5。
用骰子編號當索引、不是目前位置：範例 2 的交換是最後一步所以過；自測表第 4 列印 5 5。
滾動方向寫反：向前寫成向後，範例 1 印 4；向右寫成向左，範例 1 剛好過（先左再前頂面也是 \(3\)）、範例 2 印 2 3 1。
忘了處理交換：範例 2 印 1 3 5。