矩陣轉換 題解|APCS 2016 年 3 月中級 第 2 題
簡潔題意
矩陣有兩種操作:翻轉=第一列與最後一列交換、第二列與倒數第二列交換……(上下顛倒);旋轉=順時針轉 \(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\) 個,每一個都做它的反操作:
- 翻轉的反操作還是翻轉:子題組 1 那段「第 \(i\) 列和倒數第 \(i\) 列整列交換」原封不動。
- 順時針旋轉的反操作是逆時針旋轉。逆時針轉 \(90^\circ\) 後,新圖的 \((i, j)\) 來自舊圖的 \((j,\ cols - 1 - i)\),而且大小從 \(rows \times cols\) 變成 \(cols \times rows\)——所以每次都要另一張表
restored、搬過去、再抄回matrix,不能在原地轉。
兩張表都照上限開成 \(10 \times 10\) 的二維陣列,目前用到的大小記在 rows、cols。操作要先全部讀進陣列再倒著跑——邊讀邊做是順著做,不是倒著做。
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 10, MAX_M = 10;
int matrix[MAX_N][MAX_N]; // 目前的矩陣:只用左上角 rows x cols
int restored[MAX_N][MAX_N]; // 逆時針轉完的新矩陣
int operations[MAX_M];
int main() {
int rows, cols, operationCount;
cin >> rows >> cols >> operationCount;
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++) cin >> matrix[i][j];
for (int k = 0; k < operationCount; k++) cin >> operations[k];
for (int k = operationCount - 1; k >= 0; k--) { // 從最後一個操作倒著還原
if (operations[k] == 1) {
for (int i = 0; i < rows / 2; i++) // 翻轉:第 i 列和倒數第 i 列整列交換
for (int j = 0; j < cols; j++)
swap(matrix[i][j], matrix[rows - 1 - i][j]);
} else {
for (int i = 0; i < cols; i++) // 逆時針旋轉 90 度:大小變成 cols x rows
for (int j = 0; j < rows; j++)
restored[i][j] = matrix[j][cols - 1 - i];
swap(rows, cols); // 長寬對調
for (int i = 0; i < rows; i++) // 新矩陣抄回 matrix
for (int j = 0; j < cols; j++)
matrix[i][j] = restored[i][j];
}
}
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;
}
swap(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。 - 旋轉完忘了
swap(rows, cols):抄回matrix、之後的操作和輸出都用錯的大小——範例 1 印3 2/0 0/1 1/1 3;範例 2 印3 2/2 1/1 2/0 0。 - 把旋轉寫成轉置(
restored[i][j] = matrix[j][i]):範例 1 印1 2/3 1/1 1。 - 翻轉做成左右翻:範例 1 印
1 2/3 1/1 1;範例 2 印3 2 1/3 1 2;自測表第 3 列印3 2 1/6 5 4。 - 行末多印一個空白:本站的評測其實對行末空白寬容,但題目明寫「最後一個數字後並無空白」——用
if (j) cout << ' ';的寫法做零風險。