Codeforces 706E Working routine

发表于 分类于 Disqus：

链接

传送门

题意

给出\(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;
}
相关文章