Codeforces 706E Working routine

链接

传送门

题意

给出\(n \times m(1 \leq n, m \leq 1000)\)的矩阵,有\(q(1 \leq q \leq 10000)\)次操作,每次给出两个大小相同的且不相交无公共边的子矩阵,交换两个子矩阵,输出\(q\)次操作之后的矩阵。

思路

用十字链表储存矩阵,每个点记录下面和右面两个方向的编号。这样对于每次操作,可以在\(O(n + m)\)的时间内完成。

代码

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
84
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 1005;
const int maxm = 1002010;

int v[maxm], id[maxn][maxn];
int D[maxm], R[maxm];

int main() {
int n, m, q, num;
scanf("%d%d%d", &n, &m, &q);
num = n + m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
int x;
scanf("%d", &x);
id[i][j] = ++num;
v[num] = x;
}
}
for (int i = 1; i <= n; ++i) {
R[i] = id[i][1];
D[i] = i + 1;
for (int j = 1; j <= m; ++j) {
D[id[i][j]] = id[i + 1][j];
R[id[i][j]] = id[i][j + 1];
}
}
for (int i = 1; i <= m; ++i) {
R[i + n] = i + n + 1;
D[i + n] = id[1][i];
}
while (q--) {
int a, b, c, d, h, w;
scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &h, &w);
int p1 = a, p2 = c;
for (int i = 1; i < b; ++i) {
p1 = R[p1];
}
for (int i = 1; i < d; ++i) {
p2 = R[p2];
}
int p3 = p1, p4 = p2;
for (int i = 0; i < w; ++i) {
p3 = R[p3], p4 = R[p4];
}
for (int i = 0; i < h; ++i) {
swap(R[p1], R[p2]);
swap(R[p3], R[p4]);
p1 = D[p1], p2 = D[p2];
p3 = D[p3], p4 = D[p4];
}
p1 = b + n, p2 = d + n;
for (int i = 1; i < a; ++i) {
p1 = D[p1];
}
for (int i = 1; i < c; ++i) {
p2 = D[p2];
}
p3 = p1, p4 = p2;
for (int i = 0; i < h; ++i) {
p3 = D[p3], p4 = D[p4];
}
for (int i = 0; i < w; ++i) {
swap(D[p1], D[p2]);
swap(D[p3], D[p4]);
p1 = R[p1], p2 = R[p2];
p3 = R[p3], p4 = R[p4];
}
}
for (int i = 1; i <= n; ++i) {
int p = R[i];
for (int j = 1; j <= m; ++j) {
printf("%d ", v[p]);
p = R[p];
}
puts("");
}
return 0;
}