我认为这题应该评黄。

0x00 题目大意

给你一个 n×mn\times m 矩阵，里面元素构成排列，你可以交换任意一列任意一行，求任意次操作后两个矩阵能否相同。

0x01 解题思路

看到题面，可能没有什么思路，我们来按题目模拟一下。

设原始矩阵为：

(a1,1a1,2⋯a1,ma2,1a2,2⋯a2,m⋮⋮⋱⋮an,1an,2⋯an,m) \begin{pmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,m} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,m}\\ \end{pmatrix}

对于交换行，设交换后每一行分别为 x1,x2,⋯ ,xnx_1,x_2,\cdots ,x_n，如下：

(ax1,1ax1,2⋯ax1,max2,1ax2,2⋯ax2,m⋮⋮⋱⋮axn,1axn,2⋯axn,m) \begin{pmatrix} a_{x_1,1} & a_{x_1,2} & \cdots & a_{x_1,m} \\ a_{x_2,1} & a_{x_2,2} & \cdots & a_{x_2,m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{x_n,1} & a_{x_n,2} & \cdots & a_{x_n,m}\\ \end{pmatrix}

继续交换列，设交换后每一列分别为 y1,y2,⋯ ,yny_1,y_2,\cdots ,y_n，如下：

(ax1,y1ax1,y2⋯ax1,ymax2,y1ax2,y2⋯ax2,ym⋮⋮⋱⋮axn,y1axn,y2⋯axn,ym) \begin{pmatrix} a_{x_1,y_1} & a_{x_1,y_2} & \cdots & a_{x_1,y_m} \\ a_{x_2,y_1} & a_{x_2,y_2} & \cdots & a_{x_2,y_m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{x_n,y_1} & a_{x_n,y_2} & \cdots & a_{x_n,y_m}\\ \end{pmatrix}

仔细观察上面的矩阵，可以发现交换前在同一行（行号相同）的元素还在同一行，交换前在同一列的元素还在同一列。

因为操作次数不限，所以两个矩阵只要满足上述条件（即 AA 矩阵中同一行的元素在 BB 中也在同一行，AA 矩阵中同一列的元素在 BB 中也在同一列），就可以完成，否则不能。

0x02 代码实现

首先，m,nm,n 不确定，范围太大，需要动态处理（这在CF中很常见），可以用 vector：

1
2
3
//分配一个n行，不定列数的二维数组
vector<vector<int> >a(n);
//加列时用push_back()

接下来为了方便行列的比对，我的思路是排序后直接检验（似乎也可以哈希）。

vector 的排序可以直接 sort：

1
sort(a.begin(),a.end());

二维 vector 也可以（但需要先排第一维再第二维）sort：

1
2
3
4
for(int i=0;i<a.size();i++){
    sort(a[i].begin(),a[i].end());
}
sort(a.begin(),a.end());

0x03 AC 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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[10000001];
int b[10000001];
//#define a[i][j] a[i*(m+1)+j]
//#define b[i][j] b[i*(m+1)+j]
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i*(m+1)+j]);
        }
    }
    vector<vector<int> >line1(n);
    vector<vector<int> >col1(m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            line1[i-1].push_back(a[i*(m+1)+j]);
        }
        sort(line1[i-1].begin(),line1[i-1].end());
        //cout<<"DEBUG LINE "<<i<<" [1]   : ";
        //for(auto o:line1[i-1])cout<<o<<" ";
        //cout<<endl;

    }
    sort(line1.begin(),line1.end());
    for(int j=1;j<=m;j++){
        for(int i=1;i<=n;i++){
            col1[j-1].push_back(a[i*(m+1)+j]);
        }
        sort(col1[j-1].begin(),col1[j-1].end());
    }
    sort(col1.begin(),col1.end());
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&b[i*(m+1)+j]);
        }
    }
    vector<vector<int> >line2(n);
    vector<vector<int> >col2(m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            line2[i-1].push_back(b[i*(m+1)+j]);
        }
        sort(line2[i-1].begin(),line2[i-1].end());
    }
    sort(line2.begin(),line2.end());
    for(int j=1;j<=m;j++){
        for(int i=1;i<=n;i++){
            col2[j-1].push_back(b[i*(m+1)+j]);
        }
        sort(col2[j-1].begin(),col2[j-1].end());
    }
    sort(col2.begin(),col2.end());
    for(int i=1;i<=n;i++){
        //cout<<"DEBUG LINE "<<i<<" [1]   : ";
        //for(auto o:line1[i-1])cout<<o<<" ";
        //cout<<endl;
        //cout<<"DEBUG LINE "<<i<<" [2]   : ";
        //for(auto o:line2[i-1])cout<<o<<" ";
        //cout<<endl;
        if(line1[i-1]!=line2[i-1]){
            cout<<"NO"<<endl;
            return;
        }
    }
    for(int j=1;j<=m;j++){
        if(col1[j-1]!=col2[j-1]){
            cout<<"NO"<<endl;
            return;
        }
    }
    cout<<"YES"<<endl;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}