Codeforces 706E
题意： 给一个1000*1000的矩阵，有1000次操作，每次可以交换矩阵的两个子矩阵，保证子矩阵不重叠。输出最后的矩阵。 思路： 十字链表的版题，可以用dancing link的类似数组实现。 具体方法为，先把所有二维坐标转化为一维坐标。开两个数组ri[i]，down[i]。分别表示对于某一维下标为i的矩阵单元格，它右边和下边的格子下标是多少。 与前向星类似。 这样就可以通过只转化下标的指向，达到整块转移的目的。 源码：
#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <string> #include <algorithm> #include <iostream> #include <queue> using namespace std; const int MAXN = 1000 + 4; int ri[MAXN*MAXN], down[MAXN*MAXN]; int id[MAXN][MAXN], val[MAXN*MAXN]; int a[MAXN][MAXN]; int n, m, q; int mov(int mark, int dx, int dy) { while(dx) {mark = down[mark]; dx--; } while(dy) {mark = ri[mark]; dy--;} return mark; } void printgraph() { int mark = id[0][0]; mark = mov(mark, 1, 0); int tmark = mark; for(int i = 1 ; i <= n ; i++) { mark = tmark; tmark = mov(tmark, 1, 0); for(int j = 1 ; j <= m ; j++) { mark = mov(mark, 0, 1); printf("%d%s", val[mark], j == m ? "\n" : " "); } } } int main() { while(scanf("%d%d%d", &n, &m, &q) != EOF) { memset(ri, 0, sizeof ri); memset(down, 0, sizeof down); int cnt = 0; for(int i = 1 ; i <= n ; i++) for(int j = 1 ; j <= m ; j++) scanf("%d", &a[i][j]); for(int i = 0 ; i <= n ; i++) { for(int j = 0 ; j <= m ; j++) { id[i][j] = ++cnt; val[cnt] = a[i][j]; } } for(int i = 0 ; i <= n ; i++) for(int j = 0 ; j <= m ; j++) { if(j) ri[id[i][j - 1]] = id[i][j]; if(i) down[id[i - 1][j]] = id[i][j]; } for(int Q = 1 ; Q <= q ; Q++) { int x1, y1, x2, y2, dx, dy; scanf("%d%d%d%d%d%d", &x1, &y1, &x2, &y2, &dx, &dy); int mark1 = mov(id[0][0], x1 - 1, y1 - 1); int mark2 = mov(id[0][0], x2 - 1, y2 - 1); int p1, q1; p1 = mov(mark1, 0, 1), q1 = mov(mark2, 0, 1); int p2, q2; int p3, q3; int p4, q4; p2 = mov(mark1, dx, 1), q2 = mov(mark2, dx, 1); p3 = mov(mark1, 1, 0); q3 = mov(mark2, 1, 0); p4 = mov(mark1, 1, dy); q4 = mov(mark2, 1, dy); for(int i = 1 ; i <= dy ; i++) { swap(down[p1], down[q1]); p1 = mov(p1, 0, 1); q1 = mov(q1, 0, 1); } for(int i = 1 ; i <= dx ; i++) { swap(ri[p3], ri[q3]); p3 = mov(p3, 1, 0); q3 = mov(q3, 1, 0); } for(int i = 1 ; i <= dy ; i++) { swap(down[p2], down[q2]); p2 = mov(p2, 0, 1); q2 = mov(q2, 0, 1); } for(int i = 1 ; i <= dx ; i++) { swap(ri[p4], ri[q4]); p4 = mov(p4, 1, 0); q4 = mov(q4, 1, 0); } } printgraph(); } return 0; }