APCS 矩陣轉換 (zerojudge b266/b965)

發表於 更新於 分類於 ， 閱讀次數： 文章字數： 540 所需閱讀時間 ≈ 2 分鐘

題目網址 (多筆測資版 (https://zerojudge.tw/ShowProblem?problemid=b965))

矩陣是將一群元素整齊的排列成一個矩形，在矩陣中的橫排稱為列 (row) ，直排稱為行 (column) ，其中以 Xij 來表示 矩陣 X 中的第 i 列第 j 行的元素。 我們可以對矩陣定義兩種操作如下：
　　翻轉：即第一列與最後一列交換、第二列與倒數第二列交換、… 依此類推。
　　旋轉：將矩陣以順時針方向轉 90 度。
一個 矩陣 A 可以經過一連串的旋轉與翻轉操作後，轉換成 新矩陣 B 。 給定 矩陣 B 和一連串的操作，請算出原始的 矩陣 A 。

解題思路： 這題題目測資範圍 R,C,M 都小於 10，如果直接做的話複雜度應該就是 O (RCM)（就是按照題目的意思把輸入的矩陣反著操作），限制 2s 應該是可以順利通關

🌟因為是要從 B 推回原先的矩陣，因此需要將輸入指令倒著走一次（例如原本是 A 矩陣翻轉、翻轉、順時針旋轉 90 度得到 B 矩陣，就要將 B 矩陣逆時針旋轉 90 度、翻轉、翻轉，才能變成原先的 A 矩陣），因此現在問題就只剩下如何完成翻轉和逆時針旋轉 90 度了

  1. 翻轉：這邊是指上下翻轉，因此較為簡單，只要將第 i 列第 j 行的元素跟第 (c-i) 列第 j 行的元素交換即可，且其中 i 跟 (c-i) 會在一半的地方交會，且在 c 是奇數時 (c+1)/2 的那行可以不做任何操作，因此讓 i 從 0~c/2 執行過一次即可
  2. 逆時針旋轉 90 度：這個稍微難一點，可以想做事將左上角固定，逆時針旋轉 90 度，如此一來可以發現就是將 (i,j) 位置的元素移動到 (r-j-1,i) 逆時針旋轉90度示意圖

✏️多筆測資就只要把一開始的輸入包在 while 裡就好了

b965. 第 2 題 矩陣轉換 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;

int arr[11][11];
int c,r,m;

void turn(){
    int tmp[11][11];
    for(int i = 0; i<c; i++)
        for(int j = r-1; j>=0; j--)
            tmp[r-1-j][i]=arr[i][j];
    swap(c,r);
    for(int i = 0; i< c; i++)
        for(int j = 0; j<r; j++)
            arr[i][j] = tmp[i][j];
}

void reverse(){
    for(int i = 0; i<c/2; i++)
        for(int j = 0; j<r; j++)
            swap(arr[i][j], arr[c-1-i][j]);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    while(cin >> c >> r >> m){
        for(int i = 0; i< c; i++)
            for(int j = 0; j<r; j++)
                cin >> arr[i][j];
        bool cmd[11];
        for(int i = 0; i<m; i++) cin >> cmd[i];
        for(int i = m-1; i>=0; i--){
            if(cmd[i]) reverse();
            else turn();
        }
        cout << c << ' ' << r << '\n';
        for(int i = 0; i< c; i++){
            for(int j = 0; j<r; j++){
                cout << arr[i][j];
                if(j<r-1) cout << ' ';
            }
            cout << '\n';
        }
    }
    return 0;
}
AC的Submission～