矩阵的各种操作

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: 模拟矩阵