首页 > 代码库 > CodeForces 706E Working routine
CodeForces 706E Working routine
十字链表。
开一个十字链表，矩阵中每一格作为一个节点，记录五个量：
$s[i].L$：$i$节点左边的节点编号
$s[i].R$：$i$节点右边的节点编号
$s[i].U$：$i$节点上面的节点编号
$s[i].D$：$i$节点下面的节点编号
$s[i].V$：$i$节点存储的值
每次操作，只要把四个边上的那些边拆掉，重新连上新的边就可以了。时间复杂度：$O(qn)$。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-8;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}const int maxn=1010;int n,m,k,sz;struct X { int u,d,l,r,v; }s[maxn*maxn];int a[maxn*maxn],id[maxn][maxn];int main(){ scanf("%d%d%d",&n,&m,&k); for(int i=0;i<=n;i++) id[i][0]=sz++; for(int j=1;j<=m;j++) id[0][j]=sz++; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) id[i][j]=sz++; for(int i=1;i<=n;i++) id[i][m+1]=sz++; for(int j=1;j<=m;j++) id[n+1][j]=sz++; for(int i=0;i<=n+1;i++) { for(int j=0;j<=m+1;j++) { s[id[i][j]].l=-1; s[id[i][j]].r=-1; s[id[i][j]].u=-1; s[id[i][j]].d=-1; if(j-1>=0) s[id[i][j]].l=id[i][j-1]; if(j+1<=m+1) s[id[i][j]].r=id[i][j+1]; if(i-1>=0) s[id[i][j]].u=id[i-1][j]; if(i+1<=n+1) s[id[i][j]].d=id[i+1][j]; } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&s[id[i][j]].v); for(int i=1;i<=k;i++) { int r1,c1,r2,c2,h,w; scanf("%d%d%d%d%d%d",&r1,&c1,&r2,&c2,&h,&w); int p1,p2,t1,t2,t3,t4,P1,P2; p1=r1,p2=r2; for(int j=1;j<=c1;j++) p1=s[p1].r; for(int j=1;j<=c2;j++) p2=s[p2].r; P1=p1,P2=p2; for(int j=1;j<=w-1;j++) P1=s[P1].r; for(int j=1;j<=w-1;j++) P2=s[P2].r; for(int j=1;j<=h-1;j++) P1=s[P1].d; for(int j=1;j<=h-1;j++) P2=s[P2].d; t1=p1,t2=p2; t3=s[p1].l; t4=s[p2].l; for(int j=1;j<=h;j++) swap(s[t1].l,s[t2].l), t1=s[t1].d, t2=s[t2].d; for(int j=1;j<=h;j++) swap(s[t3].r,s[t4].r), t3=s[t3].d, t4=s[t4].d; t1=p1,t2=p2; t3=s[p1].u; t4=s[p2].u; for(int j=1;j<=w;j++) swap(s[t1].u,s[t2].u), t1=s[t1].r, t2=s[t2].r; for(int j=1;j<=w;j++) swap(s[t3].d,s[t4].d), t3=s[t3].r, t4=s[t4].r; p1=P1,p2=P2; t1=p1,t2=p2; t3=s[p1].d; t4=s[p2].d; for(int j=1;j<=w;j++) swap(s[t1].d,s[t2].d), t1=s[t1].l, t2=s[t2].l; for(int j=1;j<=w;j++) swap(s[t3].u,s[t4].u), t3=s[t3].l, t4=s[t4].l; t1=p1,t2=p2; t3=s[p1].r; t4=s[p2].r; for(int j=1;j<=h;j++) swap(s[t1].r,s[t2].r), t1=s[t1].u, t2=s[t2].u; for(int j=1;j<=h;j++) swap(s[t3].l,s[t4].l), t3=s[t3].u, t4=s[t4].u; } for(int i=1;i<=n;i++) { int p=i; for(int j=1;j<=m;j++) p=s[p].r, printf("%d ",s[p].v); printf("\n"); } return 0;}
CodeForces 706E Working routine
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。