曾彪彪的个人网站
首页
文章列表
>>
文章详情
# P4924 [1007] 魔法少女小Scarlet -- 矩阵旋转思路总结
作者:
曾彪彪
日期:
2025-07-01 01:43:01
阅读(58)
分类:
Algorithm
# 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]); } } } 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; 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; } ```
评论(0)
评论(必填)
名称(必填)
联系方式(可选)
验证码(必填)
提交
评论(必填)
名称(必填)
联系方式(可选)
验证码(必填)