Editorial for 矩陣轉換 (APCS 2016-03 中級)

簡潔題意

矩陣有兩種操作：翻轉＝第一列與最後一列交換、第二列與倒數第二列交換……（上下顛倒）；旋轉＝順時針轉 \(90^\circ\)。矩陣 \(A\) 依序做了 \(M\) 個操作變成 \(B\)。給你 \(B\)（\(R\) 列 \(C\) 行）和這 \(M\) 個操作（\(0\) 旋轉、\(1\) 翻轉，照施作順序列出），請還原 \(A\)：先輸出 \(A\) 的列數和行數，再輸出內容，每行最後一個數字後沒有空白（\(1 \le R, C, M \le 10\)）。

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

  • 子題組 1（\(30\) 分）：每個操作都是翻轉。
  • 子題組 2（\(70\) 分）：無額外限制。

先拿下子題組 1（30 分）：只有翻轉，翻回去就是了

翻轉做兩次等於沒做——所以「翻轉的反操作」還是翻轉。只有翻轉的時候，\(B\) 再翻 \(M\) 次就是 \(A\)（\(M\) 是偶數等於沒動、奇數等於翻一次；\(M \le 10\)，照翻 \(M\) 次就好，不必先算奇偶）。

翻轉怎麼寫：第 \(i\) 列和倒數第 \(i\) 列（第 \(R - 1 - i\) 列）整列交換，i 只要跑到 \(R / 2\) 之前——再往下跑會把交換過的換回來。用二維陣列裝矩陣（上冊 6.9），交換用 swap（上冊 7.6，住在 <algorithm>）。輸出的格式照題目：數字之間一個空白、行末沒有空白——if (j > 0) cout << ' '; 就是「除了每行第一個數字，前面都先印一個空白」。

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

const int MAX_N = 10;

int main() {
    int R, C, M;
    cin >> R >> C >> M;
    int a[MAX_N][MAX_N];
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++) cin >> a[i][j];

    for (int k = 0; k < M; k++) {
        int op;
        cin >> op;                 // 子題組 1 保證每個操作都是翻轉（1）
        for (int i = 0; i < R / 2; i++) {            // 第 i 列和倒數第 i 列整列交換
            for (int j = 0; j < C; j++) {
                swap(a[i][j], a[R - 1 - i][j]);
            }
        }
    }

    cout << R << ' ' << C << '\n';
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (j > 0) cout << ' ';
            cout << a[i][j];
        }
        cout << '\n';
    }
    return 0;
}

這份程式交上去，兩個範例和子題組 2 都會 WA（範例都有旋轉）——這是正常的，逐筆給分之下子題組 1 的 \(30\) 分穩穩到手。想自己驗，用下面自測表的第 3 列。

從 30 分到 100 分：從最後一個操作倒著做反操作

題目給的是做完之後的 \(B\)，要回到 \(A\) 就得把每個操作倒著解開——先穿襪子再穿鞋，脫的時候要先脫鞋再脫襪子。所以迴圈從第 \(M\) 個操作往回跑到第 \(1\) 個，每一個都做它的反操作：

  • 翻轉的反操作還是翻轉：reverse(matrix.begin(), matrix.end()) 把整個 vector 的列順序顛倒，就是上下翻轉。
  • 順時針旋轉的反操作是逆時針旋轉。13.9 的表：逆時針轉 \(90^\circ\) 後，新圖的 \((i, j)\) 來自舊圖的 \((j,\ cols - 1 - i)\)，而且大小從 \(rows \times cols\) 變成 \(cols \times rows\)——所以每次都要新開一張表 restored、搬過去、再 swap 回來（10.6），不能在原地轉。

把矩陣裝進巢狀 vector（13.1），using Matrix = vector<vector<int>>; 幫這個長型態取個短名字（12.7）。操作要先全部讀進 vector 再倒著跑——邊讀邊做是順著做，不是倒著做。

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

using Matrix = vector<vector<int>>;

int main() {
    int rows, cols, operationCount;
    cin >> rows >> cols >> operationCount;

    Matrix matrix(rows, vector<int>(cols));
    for (int i = 0; i < rows; i++)
        for (int j = 0; j < cols; j++) cin >> matrix[i][j];

    vector<int> operations(operationCount);
    for (int k = 0; k < operationCount; k++) cin >> operations[k];

    for (int k = operationCount - 1; k >= 0; k--) {          // 從最後一個操作倒著還原
        if (operations[k] == 1) {
            reverse(matrix.begin(), matrix.end());           // 翻轉：整排上下對調
        } else {
            rows = (int)matrix.size();
            cols = (int)matrix[0].size();
            Matrix restored(cols, vector<int>(rows));        // 逆時針旋轉 90 度：大小變成 cols x rows
            for (int i = 0; i < cols; i++)
                for (int j = 0; j < rows; j++)
                    restored[i][j] = matrix[j][cols - 1 - i];
            matrix.swap(restored);
        }
    }

    rows = (int)matrix.size();
    cols = (int)matrix[0].size();
    cout << rows << ' ' << cols << '\n';
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (j) cout << ' ';
            cout << matrix[i][j];
        }
        cout << '\n';
    }
    return 0;
}

輸出前的 rows、cols 要重新從 matrix 拿——轉了奇數次之後長寬是對調的。運算量小到不用算：矩陣最多 \(100\) 格、最多 \(10\) 個操作。

逆時針還是順時針，別在腦中硬記

還原用的是逆時針 restored[i][j] = matrix[j][cols - 1 - i]；如果題目要你正著做順時針，是 B[j][R - 1 - i] = A[i][j]。兩條長得像、意思相反，最保險的做法是拿一個 \(2 \times 3\) 的小矩陣代進去，看左上角的元素跑去哪裡——順時針轉完它應該在右上角。

測過再交：範例 1 有兩次旋轉，轉錯方向也會對

範例 1 的操作是「翻、轉、轉」——兩次旋轉加起來是 \(180^\circ\)，順時針逆時針都一樣，所以旋轉方向寫反的程式範例 1 照樣全對；它也是「翻轉和兩次旋轉」這種剛好可以交換順序的組合，順著做不倒著做也會對。範例 2 能抓到這兩種錯，但範例沒有「只有翻轉」和「正方形」的情況：

輸入 正確輸出 這一筆在測什麼
2 2 1 ／ 1 2 ／ 3 4 ／ 0 2 2 ／ 2 4 ／ 1 3 只有一次旋轉、而且是正方形（長寬不會提醒你轉錯）：反操作寫成順時針的程式印 3 1／4 2
1 3 2 ／ 1 2 3 ／ 0 0 1 3 ／ 3 2 1 一列轉兩次＝整個倒過來，中間經過 \(3 \times 1\)：大小變了又變回來
2 3 3 ／ 1 2 3 ／ 4 5 6 ／ 1 1 1 2 3 ／ 4 5 6 ／ 1 2 3 只有翻轉、奇數次：子題組 1 版就能驗。把翻轉做成左右翻的程式印 3 2 1／6 5 4
1 1 3 ／ 5 ／ 0 1 0 1 1 ／ 5 \(1 \times 1\) 怎麼轉都是自己

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

常犯錯誤
  • 順著操作順序做（從第 \(1\) 個做到第 \(M\) 個）：範例 1 剛好過；範例 2 印 3 2 1／3 1 2（該印 2 1 3／1 2 3）。
  • 旋轉的反操作寫成順時針：範例 1 的兩次旋轉抵銷、照樣過；範例 2 印 3 2 1／3 1 2；自測表第 1 列印 3 1／4 2。
  • 輸出的列數行數用一開始讀進來的 \(R\)、\(C\)：轉了奇數次長寬會對調——範例 1 印出 2 3 開頭、後面跟著一堆 \(0\)（拿錯的大小去讀一張 \(3 \times 2\) 的表）；範例 2 直接當掉。
  • 把旋轉寫成轉置（restored[i][j] = matrix[j][i]）：範例 1 印 1 2／3 1／1 1。
  • 翻轉做成左右翻：範例 1 印 1 2／3 1／1 1；範例 2 剛好過；自測表第 3 列印 3 2 1／6 5 4。
  • 行末多印一個空白：本站的評測其實對行末空白寬容，但題目明寫「最後一個數字後並無空白」——用 if (j) cout << ' '; 的寫法做零風險。