Photo by Fancycrave.com from Pexels

Nastya Is Transposing Matrices

题目大意就是说有两个\(n \times m\)的矩阵A和B，现在可以从矩阵A中取出一个方阵并对这个方阵进行转置，问能否通过这种操作来使得A转换为B。

首先，转置是不会影响被转置方阵的主对角线的，他只会对被转置方阵的副对角线上的元素的顺序造成影响。因此，要判断A是否能通过这样的操作转换为B，只需要判断在每一个指向右上方方向的直线上，A和B的所具有的元素是否相同即可。比方说：

\[ \begin{aligned} A_1= \begin{bmatrix} 1&2&3\\ 4&5&6\\ 7&8&9 \end{bmatrix} \ , B_1= \begin{bmatrix} 1&2&3\\ 4&7&6\\ 5&8&9 \end{bmatrix} \end{aligned} \]

这两个矩阵之间，A₁是可以通过转置得到B₁的，因为它们右上角方向上的数分别是1；2，4；3，5，7；6，8；9，只是排列顺序不一样。

但下面这两个矩阵就不行了：

\[ \begin{aligned} A_2= \begin{bmatrix} 1&2&3\\ 4&5&6\\ 7&8&9 \end{bmatrix} \ , B_2= \begin{bmatrix} 1&2&3\\ 9&7&6\\ 5&8&9 \end{bmatrix} \end{aligned} \]

其中原因不再赘述。

代码如下:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int ma[505][505];
int mb[505][505];
int arr1[505];
int arr2[505];
int n,m;
bool check(int x,int y)
{
    int i=x;
    int j=y;
    int cnt1=0;int cnt2=0;
    for(i=x,j=y;i>=1&&j<=m;i--,j++){
        arr1[cnt1++]=ma[i][j];
        arr2[cnt2++]=mb[i][j];
    }
    sort(arr1,arr1+cnt1);
    sort(arr2,arr2+cnt2);
    for(int i=0;i<cnt1;i++)
        if(arr1[i]!=arr2[i])
            return 0;
    return 1;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>ma[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>mb[i][j];
    bool flag=1;
    for(int i=1;i<=n;i++){
        if(!check(i,1)){
            flag=0;
            break;
        }
    }
    for(int i=1;i<=m;i++){
        if(!check(n,i)){
            flag=0;
            break;
        }
    }
    if(flag)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    return 0;
}