Koios1143的筆記

Zerojudge b266

發表於 分類於

Zerojudge b266

題目

https://zerojudge.tw/ShowProblem?problemid=b266

給一個經過幾個操作的矩陣，求原本矩陣的長寬以及該矩陣

可行的操作包括

  • 翻轉
  • 旋轉

特別注意到，他要的是原本的矩陣所以所有操作都要反過來做

Code

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
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
using namespace std;
int r,c,m,arr[15][15],op[15];
bool out=false;
void rotate(){
    int tmp[15][15];
    swap(r,c);
    for(int i=0 ; i<r ; i++){
        for(int j=0 ; j<c ; j++){
            tmp[i][j] = arr[j][r-i-1];
        }
    }
    swap(arr,tmp);
}
void mirror(){
    int tmp[15][15];
    for(int arr_x=r-1, tmp_x=0 ; arr_x>=0 ; arr_x--, tmp_x++){
        for(int j=0 ; j<c ; j++){
            tmp[tmp_x][j] = arr[arr_x][j];
        }
    }
    swap(arr,tmp);
}
int main(){
    while(cin>>r>>c>>m){
        if(out){
            cout<<"\n";
        }
        else{
            out=true;
        }
        for(int i=0 ; i<r ; i++){
            for(int j=0 ; j<c ; j++){
                cin>>arr[i][j];
            }
        }
        for(int i=0 ; i<m ; i++){
            cin>>op[i];
        }
        for(int i=m-1 ; i>=0 ; i--){
            if(op[i]==0){
                rotate();
            }
            else{
                mirror();
            }
        }
        cout<<r<<" "<<c<<"\n";
        for(int i=0 ; i<r ; i++){
            for(int j=0 ; j<c ; j++){
                if(j) cout<<' ';
                cout<<arr[i][j];
            }
            cout<<"\n";
        }
    }
    return 0;
}

時間複雜度分析

輸入時間複雜度為 $O(rc+m)$

翻轉與旋轉的時間複雜度皆為 $O(rc)$

每筆測資的時間複雜度為 $O(rc+m+mrc)$ 約為 $O(mrc)$