BZOJ 1142: [POI2009]Tab

1142: [POI2009]Tab

Time Limit: 40 Sec Memory Limit: 162 MB
Submit: 213 Solved: 80
[Submit][Status][Discuss]

Description

　　2个n*m矩阵，保证同一个矩阵中元素两两不同。问能否通过若干次交换两行或交换两列把第一个矩阵变成第二个。

Input

　　第一行正整数 T (1≤T≤10) 表示数据组数. 每组数据包括：第一行n m （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

鸣谢WangTianYi制作数据

[Submit][Status][Discuss]

分析

对一个矩阵交换两行的时候，显然行内元素没有发生变化；而交换两列的时候，行内元素也只是变换了顺序而已。所以得出——不论对矩阵进行什么样的变换，原本在一行内的元素现在还在一行，原本在一列的元素现在还在一列。而对于两个矩阵，如果它们每行的元素相同，定能通过若干次对列的交换使得其行内元素顺序也相同；显然列也具有相同的性质。

由此得出，我们只需要分析两个矩阵的行列是否满足元素相同即可。当然，这个问题的做法不一，或排序，或哈希。因为题目满足元素大小在-1000000到1000000之间，且一个矩阵内不存在相同元素，所以不妨直接用数组记录每个元素在A矩阵中出现的位置。假如一个元素在A矩阵的(a,b)位置出现，在B矩阵的(c,d)位置出现，我们就认为A的a行和B的c行是匹配的，A的b列和B的d列是匹配的。如果出现了一行匹配两行，就是非法的。这样就能做到稳定的O(N*M + 1000000)，显然可以过掉了。另外，最好加上读入优化，如果想上榜的话。

代码

 1 #include <bits/stdc++.h>
 2 
 3 #define N 1005
 4 #define M 1000000
 5 #define K 2000005
 6 
 7 int n, m;
 8 int a[N][N];
 9 int b[N][N];
10 int posX[K];
11 int posY[K];
12 int matchX[N];
13 int matchY[N];
14 
15 signed main(void)
16 {
17     int cas; scanf("%d", &cas);
18     
19     while (cas--)
20     {
21         scanf("%d%d", &n, &m);
22         
23         for (int i = 1; i <= n; ++i)
24             for (int j = 1; j <= m; ++j)
25                 scanf("%d", &a[i][j]), a[i][j] += M;
26         
27         for (int i = 1; i <= n; ++i)
28             for (int j = 1; j <= m; ++j)
29                 scanf("%d", &b[i][j]), b[i][j] += M;
30                 
31         memset(posX, 0, sizeof(posX));
32         memset(posY, 0, sizeof(posY));
33         
34         for (int i = 1; i <= n; ++i)
35             for (int j = 1; j <= m; ++j)
36                 posX[a[i][j]] = i, posY[a[i][j]] = j;
37                 
38         bool answer = true;
39         
40         memset(matchX, 0, sizeof(matchX));
41         memset(matchY, 0, sizeof(matchY));
42                 
43         for (int i = 1; i <= n; ++i)
44             for (int j = 1; j <= m; ++j) {
45                 const int v = b[i][j];
46                 
47                 if (!posX[v])
48                     { answer = false; break; }
49                 else if (matchX[i] && matchX[i] != posX[v])
50                     { answer = false; break; }
51                 else matchX[i] = posX[v];
52                 
53                 if (!posY[v])
54                     { answer = false; break; }
55                 else if (matchY[j] && matchY[j] != posY[v])
56                     { answer = false; break; }
57                 else matchY[j] = posY[v];
58             }
59             
60         puts(answer ? "TAK" : "NIE");
61     }
62 }

BZOJ_1142.cpp

@Author: YouSiki