题目
给出一个 \(n*m\) 的矩阵,每次交换两个等大的矩阵,输出 \(q\) 次操作后的矩阵
分析
维护向右和向下的指针,考虑最后输出只需要从每行的头指针向右跳,
那么修改实际上是将矩阵左边一列、上面一行、最后一行和最后一列向右下指针交换
时间复杂度 \(O((n+m)Q)\)
代码
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int N=1048576;
int n,m,Q,you[N],xia[N],a[N],rk[1011][1011];
int iut(){
int ans=0; char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans;
}
void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
int main(){
n=iut(),m=iut(),Q=iut();
for (int i=0;i<n+2;++i)
for (int j=0;j<m+2;++j) rk[i][j]=i*(m+2)+j;
for (int i=0;i<n+2;++i)
for (int j=0;j<m+1;++j) you[rk[i][j]]=rk[i][j+1];
for (int i=0;i<n+1;++i)
for (int j=0;j<m+2;++j) xia[rk[i][j]]=rk[i+1][j];
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j) a[rk[i][j]]=iut();
for (int T=1;T<=Q;++T){
int px=iut(),py=iut(),qx=iut(),qy=iut(),xl=iut(),yl=iut();
int tp=rk[px-1][0],tq=rk[qx-1][0];
for (int i=1;i<py;++i) tp=you[tp];
for (int i=1;i<qy;++i) tq=you[tq];
for (int Tp=tp,Tq=tq,i=0;i<xl+yl;++i)
if (i<xl){
Tp=xia[Tp],Tq=xia[Tq];
swap(you[Tp],you[Tq]);
}else{
Tp=you[Tp],Tq=you[Tq];
swap(xia[Tp],xia[Tq]);
}
for (int Tp=tp,Tq=tq,i=0;i<xl+yl;++i)
if (i>=yl){
Tp=xia[Tp],Tq=xia[Tq];
swap(you[Tp],you[Tq]);
}else{
Tp=you[Tp],Tq=you[Tq];
swap(xia[Tp],xia[Tq]);
}
}
for (int i=1;i<=n;++i){
int t=you[rk[i][0]];
for (;t!=rk[i][m+1];t=you[t]) print(a[t]),putchar(32);
putchar(10);
}
return 0;
}
标签:xia,Working,int,routine,Tp,Tq,链表,ans,iut
From: https://www.cnblogs.com/Spare-No-Effort/p/17795896.html