矩陣的各種操作

2021 年 4 月 23 日
筆記
模擬, 矩陣

題目描述

一塊 n×n 正方形的黑白瓦片的圖案要被轉換成新的正方形圖案。寫一個程式來找出將原始圖案按照以下列轉換方法轉換成新圖案的最小方式：

轉 90°：圖案按順時針轉 90°。
轉 180°：圖案按順時針轉 180°。
轉 270°：圖案按順時針轉 270°。
反射：圖案在水平方向翻轉（以中央鉛垂線為中心形成原圖案的鏡像）。
組合：圖案在水平方向翻轉，然後再按照 1∼3 之間的一種再次轉換。
不改變：原圖案不改變。
無效轉換：無法用以上方法得到新圖案。

如果有多種可用的轉換方法，請選擇序號最小的那個。

只使用上述 7 個中的一個步驟來完成這次轉換。

輸入格式

第一行一個正整數 n。

然後 n 行，每行 n 個字元，全部為 @ 或 -，表示初始的正方形。

接下來 n 行，每行 n個字元，全部為 @ 或 -，表示最終的正方形。

輸出格式

單獨的一行包括 1∼7 之間的一個數字（在上文已描述）表明需要將轉換前的正方形變為轉換後的正方形的轉換方法。

輸入輸出樣例

輸入 #1

3
@-@
---
@@-
@-@
@--
--@

輸出 #1

說明/提示

【數據範圍】
對於 1100% 的數據，1≤n≤10。

題目翻譯來自NOCOW。

USACO Training Section 1.2

解題：此題目中重點學習矩陣變換時候的問題分析思路

#include<bits/stdc++.h> //萬能頭文件
using namespace std;
int flag = 0;
char a[15][15];  //第一個輸入的矩陣
char b[15][15];  //變換後的矩陣
char c[15][15];  //要對照的矩陣
char d[15][15];  //將要存放的矩陣

int n;



//進行90度旋轉
bool work1() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            b[j][n - i + 1] = a[i][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (b[i][j] != c[i][j]) {
                return 0;
            }
        }
    }
    return 1;
}

//進行180度旋轉
//也可以看成進行了兩次work1
bool work2() {

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            b[n - i + 1][n - j + 1] = a[i][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (b[i][j] != c[i][j]) {
                return 0;
            }
        }
    }
    return 1;

}

//270度
bool work3() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            b[n - j + 1][i] = a[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (b[i][j] != c[i][j]) {
                return 0;
            }
        }
    }
    return 1;
}

//經過反射的矩陣
bool work4() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            b[i][n - j + 1] = a[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (b[i][j] != c[i][j]) {
                return 0;
            }
        }
    }
    return 1;
}


//5操作就是將4 1 2 3操作混合
bool work5() {
    work4();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = b[i][j];  //重置矩陣
        }
    }
    if (work1()) {
        return 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = b[i][j];  //重置矩陣
        }
    }
    if (work2()) {
        return 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = b[i][j];  //重置矩陣
        }
    }
    if (work3()) {
        return 1;
    }
    return 0;
}

bool work6() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (b[i][j] != c[i][j]) {
                return 0;
            }
        }

    }
    return 1;
}
bool work7() {
    cout<<7;
}

void work()
{
    if(work1())
    {
        cout<<1;
        return ;
    }
    if(work2())
    {
        cout<<2;
        return ;
    }
    if(work3())
    {
        cout<<3;
        return ;
    }
    if(work4())
    {
        cout<<4;
        return ;
    }
    if(work5())
    {
        cout<<5;
        return ;
    }
    if(work6())
    {
        cout<<6;
        return ;
    }
    cout<<7;
}

int main() {


    cin>>n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin>>a[i][j];
            d[i][j] = a[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin>>c[i][j];
        }
    }
    work();
    return 0;


}

題解來自洛谷的一個dl

設原矩陣為↓↓↓

11 12 13
21 22 23
31 32 33

那麼，經過順時針轉90度的矩陣為

31 21 11
32 22 12
33 23 13

列出ii(行)與jj(列)的關係，如下：

再進行找規律，經推敲可得

b[j][n - j + 1] = a[i][j]

相同的，設原矩陣為↓↓↓

11 12 13
21 22 23
31 32 33

那麼，經過順時針轉180度的矩陣為

33 32 31
23 22 21
13 12 11

列出ii(行)與jj(列)的關係，如下：

分析可得

b[n - i + 1][n - j + 1] = a[i][j]

其實也可以進行了兩次1（90度）操作，前者效率較高，後者程式碼短小精悍

同樣的，設原矩陣為↓↓↓

11 12 13
21 22 23
31 32 33

那麼，經過順時針轉270度的矩陣為

13 23 33
12 22 32
11 21 31

列表：

這次規律有一些難找了，是

b[n - j + 1][i] = a[i][j]

也可以看作先進行一次11操作再進行一次2操作

同樣的，設原矩陣為↓↓↓

11 12 13
21 22 23
31 32 33

那麼，經過反射的矩陣為

13 12 11
23 22 21
33 32 31

可以找出

b[i][n - j + 1] = a[i][j]

Tags: 模擬矩陣