[1007]魔法少女小Scarlet

题目描述

Scarlet 最近学会了一个数组魔法，她会在 \(n\times n\) 二维数组上将一个奇数阶方阵按照顺时针或者逆时针旋转 \(90^\circ\)。

首先，Scarlet 会把 \(1\) 到 \(n^2\) 的正整数按照从左往右，从上至下的顺序填入初始的二维数组中，然后她会施放一些简易的魔法。

Scarlet 既不会什么分块特技，也不会什么 Splay 套 Splay，她现在提供给你她的魔法执行顺序，想让你来告诉她魔法按次执行完毕后的二维数组。

输入格式

第一行两个整数 \(n,m\)，表示方阵大小和魔法施放次数。

接下来 \(m\) 行，每行 \(4\) 个整数 \(x,y,r,z\)，表示在这次魔法中，Scarlet 会把以第 \(x\) 行第 \(y\) 列为中心的 \(2r+1\) 阶矩阵按照某种时针方向旋转，其中 \(z=0\) 表示顺时针，\(z=1\) 表示逆时针。

输出格式

输出 \(n\) 行，每行 \(n\) 个用空格隔开的数，表示最终所得的矩阵

样例 #1

样例输入 #1

样例输出 #1

5 10 3 18 15
4 19 8 17 20
1 14 23 24 25
6 9 2 7 22
11 12 13 16 21

提示

对于50%的数据，满足 \(r=1\)

对于100%的数据 \(1\leq n,m\leq500\)，满足 \(1\leq x-r\leq x+r\leq n,1\leq y-r\leq y+r\leq n\)。

解答

旋转

由于顺时针旋转和逆时针旋转原理相同，下面我们以逆时针旋转为例进行说明
逆时针旋转实际上可以拆分成如下两个操作：转置 + x 逆序

1 2 3          1 4 7          3 6 9
4 5 6    =>    2 5 8    =>    2 5 8
7 8 9          3 6 9          1 4 7

明白如上原理，我们考虑矩阵中部分矩阵的情况。

对于中心点为 (x, y) 半径为 r 的小矩阵，我们进行如下推导

① 寻找 (i, j) 转置后的点：相对于左上角 (x - r, y - r)，(i, j) 的相对位置为 (i - x + r, j - y + r)，所以转置后相对于左上角的位置为 (j - y + r, i - x + r)。于是得到转置后的点位置应当为 (j - y + r + (x - r), i - x + r + (y - r)) -> (x - y + j, y - x + i)

② 寻找 (i, j) x 逆序后的点：相对于左上角 (x - r, y - r)，(i, j) 的相对位置为 (i - x + r, j - y + r)，所以 x 逆序后相对于左上角的位置为 ((x + r) - [i - (x - r)], j) -> (2x - i, j)

综上，对于点 (i, j)，转置 + x 逆序后的点为 (x + y - j, y - x + i)

实现

我们核心代码实现如下：

// 数组记录从(1, 1)开始
for (int k = 0; k < m; ++k) {
    cin >> x >> y >> r >> z;
    if(z) { // left rote
        for (int i = x - r; i <= x + r; ++i)
            for (int j = y - r; j <= y + r; ++j)
                _temp[x + y - j][y - x + i] = a[i][j];

        for (int i = x - r; i <= x + r; ++i)
            for (int j = y - r; j <= y + r; ++j)
                a[i][j] = _temp[i][j];
    } else { // right rote
        for (int i = x - r; i <= x + r; ++i)
            for (int j = y - r; j <= y + r; ++j)
                _temp[x - y + j][x + y - i] = a[i][j];

        for (int i = x - r; i <= x + r; ++i)
            for (int j = y - r; j <= y + r; ++j)
                a[i][j] = _temp[i][j];
    }
}