P3492

DDF_ · 2025-10-02 14:51:47 · 题解

题面

给两个 n \times m 的矩阵，可以交换两行，可以交换两列，求第一个矩阵可不可以用若干次操作变成第二个。

题解

不管怎么换，位于同行的总位于同行，位于同列的总位于同列，不可能拆开。

而且，这里因为元素各不相同，所以第一个矩阵中一个元素只能对应到第二个矩阵至多一个元素。

所以要判断是不是对于第一个矩阵任意一行，都在第二个矩阵中有包含相同元素的一行对应；对于第一个矩阵任意一列，都在第二个矩阵中有包含相同元素的一列对应。

如果满足上一段的结论，则绝对成立（考虑先换列，列换成对应的状态后换行即可）。

判每行，找到第一个矩阵中第 i 行第一个元素在第二个矩阵的所在行 x，然后看第一个矩阵中 i 行的元素是不是都出现在第二个矩阵的 x 行。

判每列，找到第一个矩阵中第 j 列第一个元素在第二个矩阵的所在列 y，然后看第一个矩阵中 j 列的元素是不是都出现在第二个矩阵的 y 列。

此题结。

一句闲话：这题之前我用了 vector 和 unordered_map 都被卡掉了，后面发现可以直接用数组（把低于 0 的元素加到 0 以上）。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
const int pls=1e6; 
int _;
int n,m;
int sx[N*2],sy[N*2];
int v1[1050][1050],v2[1050][1050];
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)) {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(isdigit(ch)) {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}
inline void solve() {
    n=read(),m=read();
    for(int i=1;i<=n;i++) {
        for(int j=1,x;j<=m;j++) {
            v1[i][j]=x=read();
            sx[x+pls]=0,sy[x+pls]=0;
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1,x;j<=m;j++) {
            v2[i][j]=x=read();
            sx[x+pls]=i,sy[x+pls]=j;
        }
    }
    for(int i=1;i<=n;i++) {
        int fl=sx[v1[i][1]+pls];
        for(int j=1;j<=m;j++) {
            int t=v1[i][j];
            if(!sx[t+pls]||sx[t+pls]!=fl) {puts("NIE");return;}
        }
    }
    for(int i=1;i<=m;i++) {
        int fl=sy[v1[1][i]+pls];
        for(int j=1;j<=n;j++) {
            int t=v1[j][i];
            if(!sy[t+pls]||sy[t+pls]!=fl) {puts("NIE");return;}
        }
    }
    puts("TAK");
    return;
}
int main() {
    scanf("%d",&_);
    while(_--) solve();
    return 0;
}