题解：CF706E Working routine

Charllote_ · 2025-01-22 20:54:47 · 题解

题解：CF706E Working routine

题目传送门

题目思路

暴力

我们可以枚举两个矩形中的每一个元素进行交换，具体实现不再赘叙。

时间复杂度：\operatorname{\Theta(n m q)}。

链表

发现此题中的整块移动，块的内部结构没有改变。如图：\ \ 所以我们可以把需要交换的两个块的边缘指针交换来达到整体交换的目的。

时间复杂度：\operatorname{\Theta(n q)}。

AC代码

#include<bits/stdc++.h>
using namespace std;
int k,n,m,q,fx,fy,sx,sy,h,w;
struct Node {
    int val;
    Node*right,*down;
};
Node *A[1005][1005];
inline void input() {
    ios::sync_with_stdio(false);    cin.tie(nullptr);
    cin>>n>>m>>q;
    for(int i=0; i<=n+1; i++)
        for(int j=0; j<=m+1; j++)
            A[i][j]=new Node();
    //初始化空间
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) {
            int x;  cin>>x;
            A[i][j]->val=x;
        }
    //初始化值
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            A[i][j]->down=A[i+1][j];
            A[i][j]->right=A[i][j+1];
        }
    }
    //初始化值指针
}
inline void print() {
    Node *out=A[0][1]->down;
    for(int i=1; i<=n; i++,cout<<'\n') {
        Node *nh=out->down;
        for(int j=1; j<=m; j++,out=out->right)
            cout<<(out->val)<<' ';
        out=nh;
    }
    //打印链表
}
signed main() {
    input();
    while(q--) {
        cin>>fx>>fy>>sx>>sy>>h>>w;
        Node *a=A[0][fy-1],*b=A[0][sy-1];
        for(int i=1; i<fx; i++) a=a->down;
        for(int i=1; i<sx; i++) b=b->down;
        Node *ta=a,*tb=b;
        for(int i=1; i<=w; i++) ta=ta->right,tb=tb->right,swap(ta->down,tb->down);
        for(int i=1; i<=h; i++) ta=ta->down,tb=tb->down,swap(ta->right,tb->right);
        ta=a;   tb=b;
        for(int i=1; i<=h; i++) ta=ta->down,tb=tb->down,swap(ta->right,tb->right);
        for(int i=1; i<=w; i++) ta=ta->right,tb=tb->right,swap(ta->down,tb->down);
        //交换指针
    }
    print();
    return 0;
}