钦点
问题描述
之所以续走的那些香港记者，是因为他们掌握了长者钦点董先生的关键证据，现在这份证
据落到了你的手里。
这份文件是一个 n × m 的矩形，矩形内每一个元素是一个字符串。这份文件经过了 q 次加
密，每次加密是交换两个长宽分别相等的矩形，由于长者有点老花眼，所以他加密的时候两个矩
形间任意一对元素曼哈顿距离大于 1。
由于好奇，你开始解密这份文件，方便起见，加密操作已经倒序给你，你只要按顺序操作一
遍便能解密。
当你破解完这个文件，你会发现你的生命少了做这道题的时间。
之所以续走的那些香港记者，是因为他们掌握了长者钦点董先生的关键证据，现在这份证
据落到了你的手里。
这份文件是一个 n × m 的矩形，矩形内每一个元素是一个字符串。这份文件经过了 q 次加
密，每次加密是交换两个长宽分别相等的矩形，由于长者有点老花眼，所以他加密的时候两个矩
形间任意一对元素曼哈顿距离大于 1。
由于好奇，你开始解密这份文件，方便起见，加密操作已经倒序给你，你只要按顺序操作一
遍便能解密。
当你破解完这个文件，你会发现你的生命少了做这道题的时间。
输入格式
输入文件名为
第一行，三个整数 n; m; q。
接下来的 n 行，每行 m 个非空字符串，串与串之间用一个空格隔开。
接下来的 q 行，每行六个整数 x1; y1; x2; y2; l; c 表示两个矩形的左上角和矩形的长宽 (l 对
应 x,c 对应 y)。
输出格式
输出文件名为 appoint.out。
n 行，每行 m 个非空字符串，串与串之间用一个空格隔开。表示解密后的文件。
样例输入
4 4 2
a a b b
a a b b
c c d d
c c d d
1 1 3 3 2 2
3 1 1 3 2 2
d d c c
d d c c
b b a a
b b a a
数据规模与约定
设字符串总长为 jSj。
对于前 30% 的数据，保证 jSj ≤ n × m。
对于前 60% 的数据，保证 n; m ≤ 100。
对于 100% 的数据，保证 n; m ≤ 1000; q ≤ 5000; jSj ≤ 107。
对于前 30% 的数据，保证 jSj ≤ n × m。
对于前 60% 的数据，保证 n; m ≤ 100。
对于 100% 的数据，保证 n; m ≤ 1000; q ≤ 5000; jSj ≤ 107。
题解：
用链表，对于每一个节点，d[i]表示它下方的点的编号，r[i]表示它右方点的编号。
因为每次调换区域时矩形内部的相对关系没有变化，所以不需要对矩形内部的链表进行调整。
每次调换时只要将矩形四个方向的点的链表交换即可。（详见代码）
另外注意每次查找当前位置的点，一定要通过当前链表来查找。（代码中的pos函数）而不能用坐标直接访问。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> using namespace std; template<typename T>void read(T &x) { x=0;char c=getchar(); for(;!isdigit(c);c=getchar()); for(;isdigit(c);c=getchar())x=x*10+c-'0'; } int n,m,q,sum[1000005],r[1000005],d[1000005],a[1005][1005]; char ch[10000005]; int pos(int down,int right) { int x=0; while(down--)x=d[x]; while(right--)x=r[x]; return x; } int main() { freopen("appoint.in","r",stdin); freopen("appoint.out","w",stdout); int i,j,k; int x1,x2,y1,y2,xx,yy,p1,p2; read(n);read(m);read(q); for(i=1;i<=n*m;i++) { scanf("%s",ch+sum[i-1]+1); sum[i]=sum[i-1]+strlen(ch+sum[i-1]+1); } for(i=1;i<=n;i++) for(j=1;j<=m;j++) a[i][j]=(i-1)*m+j; int tot=n*m; for(i=0;i<=n+1;i++) for(j=0;j<=m+1;j++) if((i||j)&&!a[i][j])a[i][j]=++tot; for(i=0;i<=n;i++) for(j=0;j<=m;j++) r[a[i][j]]=a[i][j+1], d[a[i][j]]=a[i+1][j]; while(q--) { read(x1);read(y1);read(x2);read(y2);read(xx);read(yy); int pos1=pos(x1-1,y1-1),Pos1=d[r[pos1]]; int pos2=pos(x2-1,y2-1),Pos2=d[r[pos2]]; for(i=1,p1=d[pos1],p2=d[pos2];i<=xx;i++,p1=d[p1],p2=d[p2])swap(r[p1],r[p2]); for(i=1,p1=r[pos1],p2=r[pos2];i<=yy;i++,p1=r[p1],p2=r[p2])swap(d[p1],d[p2]); pos1=Pos1;pos2=Pos2; for(i=1;i<yy;i++)pos1=r[pos1]; for(i=1;i<yy;i++)pos2=r[pos2]; for(i=0,p1=pos1,p2=pos2;i<xx;i++,p1=d[p1],p2=d[p2])swap(r[p1],r[p2]); pos1=Pos1;pos2=Pos2; for(i=1;i<xx;i++)pos1=d[pos1]; for(i=1;i<xx;i++)pos2=d[pos2]; for(i=0,p1=pos1,p2=pos2;i<yy;i++,p1=r[p1],p2=r[p2])swap(d[p1],d[p2]); } for(i=1,p1=d[0];i<=n;i++,p1=d[p1]) { for(j=1,p2=r[p1];j<=m;j++,p2=r[p2]) { for(k=sum[p2-1]+1;k<=sum[p2];k++) printf("%c",ch[k]); printf(" "); } printf(" "); } return 0; }