BestCoder Round

** 题目链接 ** : BestCoder Round #81 (div.2) 1002 Matrix

题意

中文题,上有链接,就不贴了。

思路

我们至少可以确定一点,无论怎么移动,在一行的数字,最终还是会在一行,在一列的数字,最终还是会在一列,无论怎么交换。
因为交换总是以整个行或者整个列为单位进行的。
确定了这个道理,我们可以用数组模拟指针指向。
用a[i] = x表示当前第i行实际是第x行。ac[i] =
num表示第i行整体增加了num。交换某行的时候,只需要交换其a数组,ac数组的对应值就好了,复杂度就降到了O(1)。
列的话同理,最后输出的时候按照行列新的指向来输出就好了。

代码

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define LL long long

int d[1009][1009];
int a[1009], ac[1009];
int b[1009], bc[1009];

int main()
{
    int T;
    cin>>T;
    for(int i=0; i<T; i++)
    {
        int n, m, q;
        memset(ac, 0, sizeof(ac));
        memset(bc, 0, sizeof(bc));
        scanf("%d%d%d", &n, &m, &q);
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                scanf("%d", &d[i][j]);
        for(int i=1; i<=n; i++)
            a[i] = i;
        for(int j=1; j<=m; j++)
            b[j] = j;
        while(q--)
        {
            int t, x, y;
            scanf("%d%d%d", &t, &x, &y);
            if(t == 1)
            {
                swap(a[x], a[y]);
                swap(ac[x], ac[y]);
            }
            else if(t == 2)
            {
                swap(b[x], b[y]);
                swap(bc[x], bc[y]);
            }
            else if(t == 3)
                ac[x] += y;
            else
                bc[x] += y;
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                printf("%d", d[a[i]][b[j]]+ac[i]+bc[j]);
                if(j != m)
                    printf(" ");
            }
            printf("\n");
        }
    }
    return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!