[POI2009]Tab
Time Limit: 40 Sec Memory Limit: 162 MB
Submit: 373 Solved: 167
[Submit][Status][Discuss]
Description
2个n*m矩阵，保证同一个矩阵中元素两两不同。问能否通过若干次交换两行或交换两列把第一个矩阵变成第二
个。
Input
第一行正整数T(1≤T≤10)表示数据组数.
每组数据包括：第一行nm（1≤n,m≤1000）2个n行m列的整数矩阵，
元素绝对值均在10^6以内
Output
每组数据输出“TAK”/“NIE”表示能/不能.
Sample Input
2
4 3
1 2 3
4 5 6
7 8 9
10 11 12
11 10 12
8 7 9
5 4 6
2 1 3
2 2
1 2
3 4
5 6
7 8
4 3
1 2 3
4 5 6
7 8 9
10 11 12
11 10 12
8 7 9
5 4 6
2 1 3
2 2
1 2
3 4
5 6
7 8
Sample Output
TAK
NIE
NIE
HINT
Source
题解：如果可以知道两个矩阵的最小表示就可以比较是否相同了，现将最小的数放到最左上角，因为每个数不同
然后，按照行的开头，再按第一行的各列来排序，就可以了，这样二维的位置，就已经被二维关键字排过了，是唯一的。
然后比较即可，时间复杂度貌似是n^3的，但是过了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std; const int N=; int a[N][N],b[N][N],n,m; int read()
{
int x=,f=;char ch=getchar();
while (ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
} void work1()
{
int x,y,mn=1e7;
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
if (a[i][j]<mn) mn=a[i][j],x=i,y=j;
if (x!=) for (int i=;i<=m;i++) swap(a[x][i],a[][i]);
if (y!=) for (int i=;i<=n;i++) swap(a[i][y],a[i][]);
for (int i=;i<n;i++)
{
int mn=1e7,x;
for (int j=i;j<=n;j++)
if (a[j][]<mn) mn=a[j][],x=j;
if (i!=x) for (int j=;j<=m;j++) swap(a[i][j],a[x][j]);
}
for (int i=;i<m;i++)
{
int mn=1e7,x;
for (int j=i;j<=m;j++)
if (a[][j]<mn) mn=a[][j],x=j;
if (i!=x) for (int j=;j<=n;j++) swap(a[j][i],a[j][x]);
}
} void work2()
{
int x,y,mn=1e7;
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
if (b[i][j]<mn) mn=b[i][j],x=i,y=j;
if (x!=) for (int i=;i<=m;i++) swap(b[x][i],b[][i]);
if (y!=) for (int i=;i<=n;i++) swap(b[i][y],b[i][]);
for (int i=;i<n;i++)
{
int mn=1e7,x;
for (int j=i;j<=n;j++)
if (b[j][]<mn) mn=b[j][],x=j;
if (i!=x) for (int j=;j<=m;j++) swap(b[i][j],b[x][j]);
}
for (int i=;i<m;i++)
{
int mn=1e7,x;
for (int j=i;j<=m;j++)
if (b[][j]<mn) mn=b[][j],x=j;
if (i!=x) for (int j=;j<=n;j++) swap(b[j][i],b[j][x]);
}
} int main()
{
int T=read();
while (T--)
{
n=read(),m=read();
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
a[i][j]=read();
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
b[i][j]=read();
work1();work2();
int flag=;
for (int i=;i<=n;i++)
{
for (int j=;j<=m;j++)
if (a[i][j]!=b[i][j])
{
flag=;break;
}
if (flag) break;
}
if (flag) puts("NIE");
else puts("TAK");
}
return ;
}