[POI2009]Tab

Time Limit: 40 Sec  Memory Limit: 162 MB

Submit: 373  Solved: 167

[][][]

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

Sample Output

TAK

NIE

HINT

 

Source

 

题解：如果可以知道两个矩阵的最小表示就可以比较是否相同了，现将最小的数放到最左上角，因为每个数不同

　　　然后，按照行的开头，再按第一行的各列来排序，就可以了，这样二维的位置，就已经被二维关键字排过了，是唯一的。

　　　然后比较即可，时间复杂度貌似是n^3的，但是过了。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7  8 const int N=1005; 9 10 int a[N][N],b[N][N],n,m;11 12 int read()13 {14     int x=0,f=1;char ch=getchar();15     while (ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}16     while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}17     return x*f;18 }19 20 void work1()21 {22     int x,y,mn=1e7;23     for (int i=1;i<=n;i++)24         for (int j=1;j<=m;j++)25             if (a[i][j]