# APCS實作題2016年3月第2題：矩陣轉換

> 第1版：2023年2月10日
> 第2版：2023年6月9日，加上 C++ 程式碼
> 作者：王一哲
> 題目來源：[105年3月5日實作題第2題](https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2020/10/APCS-%E5%AF%A6%E4%BD%9C%E9%A1%8C-2016.03.05.pdf)
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=b266)

<br />

## 題目

### 問題描述

矩陣是將一群元素整齊的排列成一個矩形，在矩陣中的橫排稱為列 (row)，直排稱為行 (column)，其中以 $X_{ij}$ 來表示矩陣 $X$ 中的第 $i$ 列第 $j$ 行的元素。如圖一中，$X_{32} = 6$。

我們可以對矩陣定義兩種操作如下：

- 翻轉：即第一列與最後一列交換、第二列與倒數第二列交換、……依此類推。
- 旋轉：將矩陣以順時針方向轉 90 度。

例如：矩陣 $X$ 翻轉後可得到 $Y$，將矩陣 $Y$ 再旋轉後可得到 $Z$。

<img height="60%" width="60%" src="https://i.imgur.com/Yt1SpYc.png" style="display: block; margin-left: auto; margin-right: auto;"/>
<br />

一個矩陣 $A$ 可以經過一連串的旋轉與翻轉操作後，轉換成新矩陣 $B$。如圖二中，$A$
經過翻轉與兩次旋轉後，可以得到 $B$。給定矩陣 $B$ 和一連串的操作，請算出原始的
矩陣 $A$。

<img height="80%" width="80%" src="https://i.imgur.com/b9lKZEu.png" style="display: block; margin-left: auto; margin-right: auto;"/>
<br />

### 輸入格式

第一行有三個介於 1 與 10 之間的正整數 $R$, $C$, $M$。接下來有 $R$ 行(line)是矩陣 $B$ 的內容，每一行(line)都包含 $C$ 個正整數，其中的第 $i$ 行第 $j$ 個數字代表矩陣 $B_{ij}$ 的值。在矩陣內容後的一行有 $M$ 個整數，表示對矩陣 $A$ 進行的操作。第 $k$ 個整數 $m_k$ 代表第 $k$ 個操作，如果 $m_k = 0$ 則代表旋轉，$m_k = 1$ 代表翻轉。同一行的數字之間都是以一個空白間格，且矩陣內容為 0~9 的整數。
<br />

### 輸出格式

輸出包含兩個部分。第一個部分有一行，包含兩個正整數 $R'$ 和 $C'$ ，以一個空白隔開，分別代表矩陣 $A$ 的列數和行數。接下來有 $R'$ 行，每一行都包含 $C'$ 個正整數，且每一行的整數之間以一個空白隔開，其中第 $i$ 行的第 $j$ 個數字代表矩陣 $A_{ij}$ 的值。每一行的最後一個數字後並無空白。
<br />

### 範例一：輸入

3 2 3
1 1
3 1
1 2
1 0 0

### 範例一：正確輸出

3 2
1 1
1 3
2 1

（說明）如圖二所示
<br />

### 範例二：輸入

3 2 2
3 3
2 1
1 2
0 1

### 範例二：正確輸出

2 3
2 1 3
1 2 3

（說明）

<img height="40%" width="40%" src="https://i.imgur.com/0Wt3m1X.png" style="display: block; margin-left: auto; margin-right: auto;"/>
<br />

### 評分說明

輸入包含若干筆測資，每一筆測資的執行時間限制(time limit)均為 2 秒，依
正確通過測資筆數給分。其中：
第 1 子題組 30 分，其每個操作都是翻轉。
第 2 子題組 70 分，操作有翻轉也有旋轉。
<br /><br />

## 分析

若矩陣A為維度為 $M \times N$（M rows, N columns)
$$
A =
\begin{bmatrix}
A_{00} & A_{01} & A_{02} & A_{03} \\
A_{10} & A_{11} & A_{12} & A_{13} \\
A_{20} & A_{21} & A_{22} & A_{23}
\end{bmatrix}
$$

將矩陣A順時鐘方向旋轉後儲存為矩陣B

$$
B =
\begin{bmatrix}
B_{00} & B_{01} & B_{02} \\
B_{10} & B_{11} & B_{12} \\
B_{20} & B_{21} & B_{22} \\
B_{30} & B_{31} & B_{32}
\end{bmatrix}
{} =
\begin{bmatrix}
A_{20} & A_{10} & A_{00} \\
A_{21} & A_{11} & A_{01} \\
A_{22} & A_{12} & A_{02} \\
A_{23} & A_{13} & A_{03}
\end{bmatrix}
$$

因此矩陣B與旋轉前的矩陣A索引值對應的關係為 $(i, j) = (M - j -1, i)$。
<br />

將矩陣A上下翻轉後儲存為矩陣B

$$
B =
\begin{bmatrix}
B_{00} & B_{01} & B_{02} & B_{03}\\
B_{10} & B_{11} & B_{12} & B_{13}\\
B_{20} & B_{21} & B_{22} & B_{23}
\end{bmatrix}
{} =
\begin{bmatrix}
A_{20} & A_{21} & A_{22} & A_{23}\\
A_{10} & A_{11} & A_{12} & A_{13}\\
A_{00} & A_{01} & A_{02} & A_{03}
\end{bmatrix}
$$

因此矩陣B與上下翻轉前的矩陣A索引值對應的關係為 $(i, j) = (M - i - 1, j)$。

最後要特別注意一點，**本題是要從操作後的矩陣逆推回原來的矩陣，所有的操作步驟順序相反，矩陣向逆時鐘方向轉回去**。
<br /><br />

## Python 程式碼

### 原版的題目

"""
 APCS 105年3月實作題2：矩陣轉換
 日期：2023/2/10
 作者：王一哲
 題目來源：https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2020/10/APCS-%E5%AF%A6%E4%BD%9C%E9%A1%8C-2016.03.05.pdf
"""
# 逆時鐘方向轉回來
def rotate(matrix):
    rows = len(matrix[0])
    columns = len(matrix)
    matrix2 = [[None]*columns for _ in range(rows)]
    for i in range(columns):
        for j in range(rows):
            matrix2[rows - j - 1][i] = matrix[i][j]
    return matrix2

# 上下翻轉
def updown(matrix):
    rows = len(matrix)
    columns = len(matrix[0])
    matrix2 = [[None]*columns for _ in range(rows)]
    for i in range(rows):
        for j in range(columns):
            matrix2[i][j] = matrix[rows - i - 1][j]
    return matrix2

# 印出矩陣
def printMatrix(matrix):
    rows = len(matrix)
    columns = len(matrix[0])
    for i in range(rows):
        for j in range(columns):
            if j == columns - 1: print("{:d}".format(matrix[i][j]))
            else: print("{:d}".format(matrix[i][j]), end=" ")

# 輸入R、C、M，輸入矩陣列數R、每列元素數量C、操作次數M，並用半型空格分隔
R, C, M = map(int, input().split())

# 輸入陣列B資料，輸入矩陣每列的內容，並用半型空格分隔
B = []
for _ in range(R):
    B.append(list(map(int, input().split())))

# 輸入操作 operates，輸入操作，0代表順時鐘方向旋轉，1代表上下翻轉，並用半型空格分隔，操作順序要反過來
operates = list(map(int, input().split()))
operates.reverse()

# 反過來操作，得到原來的矩陣
A = B.copy()
for operate in operates:
    if operate == 0:
        A = rotate(A)
    elif operate == 1:
        A = updown(A)

# 輸出結果
print("{:d} {:d}".format(len(A), len(A[0])))
printMatrix(A)

<br />

1. 第8 ~ 15行：自訂函式 rotate，將矩陣逆時鐘方向轉回去。假設輸入的矩陣（旋轉後的矩陣B）維度為 $N \times M$，先産生一個所有元素皆為 None、維度為 $M \times N$ 的矩陣，用來接收對應索引值的元素，最後輸出為原來的矩陣（旋轉前的矩陣A）。
2. 第18 ~ 25行：自訂函式 updown，將矩陣上下翻轉。由於翻轉前後的矩陣維度相同，若輸入的矩陣（翻轉後的矩陣B）維度為 $M \times N$，先産生一個所有元素皆為 None、維度為 $M \times N$ 的矩陣，用來接收對應索引值的元素，最後輸出為原來的矩陣（翻轉前的矩陣A）。
3. 第28 ~ 34行：自訂函式 printMatrix，依序印出各個元素，相鄰兩個元素之間用半型空格分開，特別注意**每一列的元素之後沒有空格、直接換行**。其中第33、34行也可以寫成這樣

    print(matrix[i][j], end="\n" if j == columns-1 else " ")

5. 第37行：由鍵盤輸入資料，分別儲存到變數R、C、M。
6. 第40 ~ 42行：由鍵盤輸入R行的資料，用 list 格式儲存到操作後的矩陣B。
7. 第45 ~ 46行：由鍵盤輸入操作步驟，用 list 格式儲存到 operates，但是題目要反序操作變回原來的矩陣，要再用 reverse() 將 operates 中的資料順序顛倒。
8. 第49 ~ 54行：先將矩陣B的資料複製到矩陣A，由 operates 依序讀取操作步驟，將矩陣A變為操作前的樣子。
9. 第57行：印出原來的矩陣維度。
10. 第58行：用自訂函式 printMatrix 印出矩陣的元素。
11. ZeroJudge 測試結果：花費時間約為 18 ms，使用記憶體 3.4 MB，通過測試。
<br /><br />

## 加強版：測資有多個矩陣

> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=b965)

<br />

這是上一題的加強版，測資中包含多個矩陣，以下是我的寫法。
<br />

"""
 APCS 105年3月實作題2：矩陣轉換，每筆測試資料中有多筆矩陣及操作的資料
 日期：2023/2/10
 作者：王一哲
 題目來源：https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2020/10/APCS-%E5%AF%A6%E4%BD%9C%E9%A1%8C-2016.03.05.pdf
"""
import sys
# 逆時鐘方向轉回來
def rotate(matrix):
    rows = len(matrix[0])
    columns = len(matrix)
    matrix2 = [[None]*columns for _ in range(rows)]
    for i in range(columns):
        for j in range(rows):
            matrix2[rows - j - 1][i] = matrix[i][j]
    return matrix2

# 上下翻轉矩陣
def updown(matrix):
    rows = len(matrix)
    columns = len(matrix[0])
    matrix2 = [[None]*columns for _ in range(rows)]
    for i in range(rows):
        for j in range(columns):
            matrix2[i][j] = matrix[rows - i - 1][j]
    return matrix2

# 印出矩陣，每一列最後一個數字之後沒有空格
def printMatrix(matrix):
    rows = len(matrix)
    columns = len(matrix[0])
    for i in range(rows):
        for j in range(columns):
            if j < columns - 1: print("{:d}".format(matrix[i][j]), end=" ")
            else: print("{:d}".format(matrix[i][j]))

def action(data):
    # 輸入R、C、M，輸入矩陣列數R、每列元素數量C、操作次數M，並用半型空格分隔
    R, C, M = data[0][0], data[0][1], data[0][2]
    # 輸入陣列B資料，輸入矩陣每列的內容，並用半型空格分隔
    B = []
    for i in range(1, R+1):
        B.append(data[i])
    # 輸入操作 operates，輸入操作，0代表順時鐘方向旋轉，1代表上下翻轉，並用半型空格分隔
    operates = data[R+1]
    operates.reverse()
    # 操作矩陣
    A = B.copy()
    for operate in operates:
        if operate == 0:
            A = rotate(A)
        elif operate == 1:
            A = updown(A)
    # 輸出結果
    print("{:d} {:d}".format(len(A), len(A[0])))
    printMatrix(A)

# 輸入資料
data, matrices = [], []
while True:
    try:
        line = list(map(int, sys.stdin.readline().split()))
        if not line: break
        data.append(line)
    except EOFError:
        pass

# 分割每個矩陣的資料
i = 0
while i < len(data): 
    n = data[i][0]
    matrices.append(data[i:i+n+2])
    i = i+n+2

# 操作矩陣
for matrix in matrices: action(matrix)

<br />

1. 自訂函式 rotate、updown、printMatrix 都與上一題的程式碼相同，直接沿用。
2. 第37 ~ 56行：自訂函式 action，包含讀取輸矩陣列數R、每列元素數量C、操作次數M、矩陣內容、操作步驟、反操作、印出結果。
3. 第59 ~ 66行：由標準輸入讀取資料，原來的寫法是用 input，但是在 ZeroJudge 上測試時會發生錯誤，因此在程式一開始 **import sys**，第62行後半段改寫成 **sys.stdin.readlin().split()**，並且將讀取資料的部分包到 try 裡面，發生 **EOFError** 時執行 pass，程式才不會卡住。
4. 第69 ~ 73行：分割讀進來的資料 data，每個矩陣的資料，包含R、C、M、元素、操作，存成一個一維串列，再包到二維串列 matrices 之中。
5. 第76行：由 matrices依序讀取每個矩陣的資料，引用自訂函式 action，變回原來的矩陣並印出維度、元素。
6. ZeroJudge 測試結果：第一筆測資花費時間約為 36 ms，使用記憶體 4.2 MB；第二筆測資花費時間約為 0.2 s，使用記憶體 5.9 MB，通過測試。
<br /><br />

## C++ 程式碼

### 原版的題目

#include <iostream>
using namespace std;

void swap(int&, int&); // 交換數值
void rotate();         // 逆時鐘方向轉回來
void updown();         // 上下翻轉
void printMatrix();    // 印出矩陣

int R, C, M;
int **matrix;

int main(int argc, char* argv[]) {
    // 輸入R、C、M，輸入矩陣列數R、每列元素數量C、操作次數M，並用半型空格分隔
    cin >> R >> C >> M;
    // 輸入陣列B資料，輸入矩陣每列的內容，並用半型空格分隔
    matrix = new int*[R];
    for(int i=0; i<R; i++) {
        matrix[i] = new int[C];
        for(int j=0; j<C; j++) {
            cin >> matrix[i][j];
        }
    }
    // 輸入操作 operates，輸入操作，0代表順時鐘方向旋轉，1代表上下翻轉，並用半型空格分隔，操作順序要反過來
    int operates[M];
    for(int i=0; i<M; i++) {
        cin >> operates[M-i-1];
    }
    // 還原矩陣
    for(int i=0; i<M; i++) {
        if (operates[i] == 0) rotate();
        else if (operates[i] == 1) updown();
    }
    // 輸出題目要求的內容
    cout << R << " " << C << endl;
    printMatrix();
    return 0;
}

void swap(int& a, int& b) {
    int tmp = a;
    a = b;
    b = tmp;
}

void rotate() {
    int** newMatrix = new int*[C];
    for(int i=0; i<C; i++) {
        newMatrix[i] = new int[R];
        for(int j=0; j<R; j++) {
            newMatrix[i][j] = matrix[j][C-i-1];
        }
    }
    matrix = newMatrix;
    swap(R, C);
}

void updown() {
    for(int i=0; i<R/2; i++) {
        for(int j=0; j<C; j++) {
            swap(matrix[i][j], matrix[R-i-1][j]);
        }
    }
}

void printMatrix() {
    for(int i=0; i<R; i++) {
        for(int j=0; j<C; j++) {
            if (j < C-1) 
                cout << matrix[i][j] << " ";
            else
                cout <<  matrix[i][j] << endl;
        }
    }
}

<br />

1. 第4、39 ~ 43行：自訂函式 swap，用來交換數值。
2. 第5、45 ~ 55行：自訂函式 rotate，將矩陣逆時鐘方向轉回去。輸入的資料是為旋轉後的矩陣 mateix，維度為 $N \times M$；函式中先産生一個維度為 $M \times N$ 的矩陣 newMatrix，用來接收旋轉前的矩陣資料；再將 newMatrix 的資料傳給 matrix。
3. 第6、57 ~ 63行：自訂函式 updown，利用自訂函式 swap 將矩陣上下翻轉，。
4. 第7、65 ~ 74行：自訂函式 printMatrix，依序印出各個元素，相鄰兩個元素之間用半型空格分開，特別注意**每一列的元素之後沒有空格、直接換行**。
5. 第9行：定義全域變數 R、C、M。
6. 第10行：定義全域變數 matrix，為二維陣列。
7. 第14行：由鍵盤輸入資料，分別儲存到變數R、C、M。
8. 第16 ~ 22行：由鍵盤輸入資料操作後的矩陣 matrix。
10. 第24 ~ 27行：由鍵盤輸入操作步驟，儲存到一維陣列 operates，但是題目要反序操作變回原來的矩陣，operates 中的資料與輸入資料順序相反。
11. 第29 ~ 32行：由 operates 依序讀取操作步驟，將矩陣 matrix 變為操作前的樣子。
12. 第34行：印出原來的矩陣維度。
13. 第35行：用自訂函式 printMatrix 印出矩陣的元素。
14. ZeroJudge 測試結果：花費時間約為 2 ms，使用記憶體 324 kB，通過測試。
<br /><br />

---

###### tags:`APCS`、`Python`