曾彪彪的个人博客 -- # P4924 [1007] 魔法少女小Scarlet -- 矩阵旋转思路总结

# P4924 [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

```
5 4
2 2 1 0
3 3 1 1
4 4 1 0
3 3 2 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$。

这道题我提交了好多次，就是无法AC，后来拿了别人AC的代码，对比自己的代码，才发现自己题目意思理解错了。题目意思是，输入任意x,y,r,z，以x,y为中心，以2r-1为矩阵，顺时针或逆时针旋转后，在输出结果。我根据题目提供的测试数据，理解成以x,x为中心，忽略了y，所以题目理解错误。第一次编写的错误代码如下：
``` c++ 
/**
start time: 8:45
End time:
Type: simulator
Solution:
- clockwise rotation
- swap the elements by diagonal
- swap the elements vertically
-

- anti-clockwase rotation  invoke
test case:
-
-
-
-
first submit score: 100
cause:

**/

#include <bits/stdc++.h>
using namespace std;

void rotate(vector<vector<int>> &s, int m, int n)
{
    for (int i = m; i <= n; i++)
    {
        for (int j = m; j < i; j++)
        {
            swap(s[i][j], s[j][i]);
        }
    }
    for (int i = m; i <= n; i++)
    {
        for (int j = m; j < (m + n) / 2; j++)
        {
            swap(s[i][j], s[i][n + m - j]);
        }
    }
}

void print(vector<vector<int>> &s)
{
    for (int i = 1; i < s.size(); i++)
    {
        for (int j = 1; j < s.size(); j++)
        {
            cout << s[i][j] << " ";
        }
        cout << endl;
    }
}

int main()
{
    // freopen("C:/Users/zengsam/Downloads/P1042_2.in", "r", stdin);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> s(n + 1, vector<int>(n + 1));
    int index = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            s[i][j] = index++;
        }
    }
    while (m--)
    {
        int x, y, r, z;
        cin >> x >> y >> r >> z;
        int left = x - r;
        int right = x + r;
        if (z == 0)
        {
            rotate(s, left, right);
            // print(s);
            cout << endl;
        }
        else
        {
            rotate(s, left, right);
            rotate(s, left, right);
            rotate(s, left, right);
            // print(s);
            cout << endl;
        }
    }
    print(s);
    return 0;
}

```
后来修改逻辑，发现还是做不对，原因是对矩阵旋转知识理解不扎实，现将矩阵旋转方法归纳总结如下：

1. 矩阵旋转
1.1 顺时针旋转
1.1.1 使用临时数组，直接旋转 
1.1.2 不使用临时数组
1.1.2.1 逐个旋转
1.1.2.2 沿主对角线转置（左上到右下对角线对称元素交换位置），再左右翻转
--- 
1.2 逆时针旋转
1.2.1 使用临时数组，直接旋转 
1.2.2 不使用临时数组
1.2.2.1 逐个旋转
1.2.2.2 沿主对角线转置（左上到右下对角线对称元素交换位置），再上下翻转
1.2.2.3 顺时针旋转3次

主要卡在下标转换错误，在草稿纸上画半天才推导出来。AC代码如下：
```c++
/**
start time: 8:45
End time:
Type: simulator
Solution:
- clockwise rotation
- swap the elements by diagonal
- swap the elements vertically
-

- anti-clockwase rotation  invoke
test case:
-
-
-
-
first submit score: 100
cause:

**/

#include <bits/stdc++.h>
using namespace std;

void rotate(vector<vector<int>> &s, int m, int n, int o, int p)
{
    for (int i = m; i <= n; i++)
    {
        for (int j = o; j < o + i - m; j++)
        {
            swap(s[i][j], s[m + j - o][o + i - m]);
        }
    }
    for (int i = m; i <= n; i++)
    {
        for (int j = o; j < (o + p) / 2; j++)
        {
            swap(s[i][j], s[i][o + p - j]);
        }
    }
}

int main()
{
    // freopen("C:/Users/zengsam/Downloads/P1042_2.in", "r", stdin);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> s(n + 1, vector<int>(n + 1));
    int index = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            s[i][j] = index++;
        }
    }
    while (m--)
    {
        int x, y, r, z;
        cin >> x >> y >> r >> z;
        int left = x - r;
        int right = x + r;
        int top = y - r;
        int down = y + r;
        if (z == 0)
        {
            rotate(s, left, right, top, down);
            // print(s);
            cout << endl;
        }
        else
        {
            rotate(s, left, right, top, down);
            rotate(s, left, right, top, down);
            rotate(s, left, right, top, down);
            // print(s);
            cout << endl;
        }
    }
    print(s);
    return 0;
}

```

因为矩阵旋转掌握得不够好，所以把所有矩阵旋转的方法全部再实现一遍：
```c++
/**
start time: 8:45
End time:
Type: simulator
Solution:
- clockwise rotation
- swap the elements by diagonal
- swap the elements vertically
-

- anti-clockwase rotation  invoke
test case:
-
-
-
-
first submit score: 100
cause:

**/

#include <bits/stdc++.h>
using namespace std;

/***
 * need extra space, easy to understand
 */
vector<vector<int>> rotateWithExtraSpace(vector<vector<int>> s)
{
    vector<vector<int>> result(s.size(), vector<int>(s.size()));
    for (int i = 0; i < s.size(); i++)
    {
        for (int j = 0; j < s[0].size(); j++)
        {
            result[j][s.size() - i - 1] = s[i][j];
        }
    }
    return result;
}

/*****
 * hard to understand, save space
 */
vector<vector<int>> rotateByLoop(vector<vector<int>> s)
{
    int n = s.size();
    for (int i = 0; i < n / 2; i++)
    {
        for (int j = i; j < n - i - 1; j++)
        {
            int temp = s[i][j];
            s[i][j] = s[n - j - 1][i];
            s[n - j - 1][i] = s[n - i - 1][n - j - 1];
            s[n - i - 1][n - j - 1] = s[j][n - i - 1];
            s[j][n - i - 1] = temp;
        }
    }
    return s;
}

/*****
 * easy to understand, save space
 */
vector<vector<int>> rotateByExchange(vector<vector<int>> s)
{
    int n = s.size();
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            swap(s[i][j], s[j][i]);
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n / 2; j++)
        {
            swap(s[i][j], s[i][n - 1 - j]);
        }
    }
    return s;
}

/*****
 * easy to understand, save space
 */
vector<vector<int>> rotateWithAntiClockWise(vector<vector<int>> s)
{
    int n = s.size();
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            swap(s[i][j], s[j][i]);
        }
    }
    for (int i = 0; i < n/2; i++)
    {
        for (int j = 0; j < n; j++)
        {
            swap(s[i][j], s[n - 1 - i][j]);
        }
    }
    return s;
}

void print(vector<vector<int>> &s)
{
    for (int i = 0; i < s.size(); i++)
    {
        for (int j = 0; j < s.size(); j++)
        {
            cout << s[i][j] << " ";
        }
        cout << endl;
    }
}

int main()
{
    // freopen("C:/Users/zengsam/Downloads/P1042_2.in", "r", stdin);
    int m, n;
    cin >> m >> n;
    vector<vector<int>> s(n, vector<int>(n));
    int index = 1;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            s[i][j] = index++;
        }
    }
    print(s);
    cout << endl;
    // vector<vector<int>> result = rotateWithExtraSpace(s);
    // vector<vector<int>> result = rotateByLoop(s);
    vector<vector<int>> result = rotateWithAntiClockWise(s);
    print(result);
    return 0;
}

```

# P4924 [1007] 魔法少女小Scarlet -- 矩阵旋转思路总结

评论(0)