链表和数组是两对极端，链表定位慢，增删交换快。而块状链表是二者的综合体 这里大概是一维链表高效交换的二维版本。 维护一个十字链表即可。 十字链表没有必要记录每个元素上下左右的所有元素，只需要记录下和右即可，维持要增加第0行和0列。 对于矩阵交换，暴力的更新整个矩阵周长两边的节点的值即可，复杂度 O(q×(m+n)
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define pr(x) cout << #x << ": " << x << " " #define pl(x) cout << #x << ": " << x << endl; struct node { int v, r, d; node (){} node (int V, int R, int D): v(V), r(R), d(D){} } nodes[1009 * 1009]; struct jibancanyang { int n, m, q; int f(int i, int j) { return i * (m + 1) + j; } int g(int i, int j) { int k = 0; while (i--) k = nodes[k].d; while (j--) k = nodes[k].r; return k; } void print() { int k = 0; for (int i = 0; i < n; ++i) { k = nodes[k].d; for (int j = 0, t = k; j < m; ++j) { t = nodes[t].r; printf("%d ", nodes[t].v); } puts(""); } } void build() { for (int i = 0; i <= n; ++i) { for (int j = 0; j <= m; ++j) { nodes[f(i, j)] = node(0, f(i, j + 1), f(i + 1, j)); } } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { scanf("%d", &nodes[f(i, j)].v); } } while (q--) { int a, b, x, y, l, w; scanf("%d%d%d%d%d%d", &a, &b, &x, &y, &w, &l); a = g(a - 1, b - 1), b = g(x - 1, y - 1); // pr(nodes[a].v), pr(nodes[a].r), pl(nodes[a].d); x = a, y = b; for (int i = 0; i < l; ++i) { a = nodes[a].r, b = nodes[b].r; swap(nodes[a].d, nodes[b].d); } for (int i = 0; i < w; ++i) { a = nodes[a].d, b = nodes[b].d; swap(nodes[a].r, nodes[b].r); } for (int i = 0; i < w; ++i) { x = nodes[x].d, y = nodes[y].d; swap(nodes[x].r, nodes[y].r); } for (int i = 0; i < l; ++i) { x = nodes[x].r, y = nodes[y].r; swap(nodes[x].d, nodes[y].d); } } print(); } }ac; int main() { #ifdef LOCAL freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif scanf("%d%d%d", &ac.n, &ac.m, &ac.q); ac.build(); return 0; }