这个问题花费了我相当长的时间,但如果你采用正确的方法,它就非常简单。
请注意,这仅适用于方阵。矩形将需要使用其他算法(转置和翻转)。如果要原地完成,则可能需要暂时调整数组大小。
简化问题
考虑以下矩阵:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
将图形旋转90度,并只看角落上的数字(1、4、16和13)。如果您难以想象,请用便利贴帮助自己。
现在,我们来考虑下面这个:
1 - - 2
- - - -
- - - -
4 - - 3
将它旋转90度,注意数字如何以循环方式旋转:2变成1,3变成2,4变成3,1变成4。
旋转角落
为了旋转角落,需要用第一个角来定义所有角落:
- 第一个角是
(i, j)
- 第二个角是
(SIZE - j, i)
- 第三个角是
(SIZE - i, SIZE - j)
- 第四个角是
(j, SIZE - i)
请注意,数组从0开始,因此SIZE
也需要从0开始(即需要减去1)。
现在您已经理解了旋转角落的概念,我们将扩展“旋转角落”到“旋转象限”的思想。同样的原则适用。
代码
您需要确保没有任何数字被覆盖。这意味着您需要同时旋转4个数字。
#include <algorithm>
#include <numeric>
#include <vector>
using std::iota;
using std::swap;
using std::vector;
void rotate4(int &a, int &b, int &c, int &d)
{
swap(a, b);
swap(b, c);
swap(c, d);
}
void rotateMatrix(vector<vector<int>>& m) {
int n = m.size();
for (int i = 0; i < n/2; i++) {
for (int j = 0; j < (n + 1)/2; j++) {
int r_i = (n - 1) - i;
int r_j = (n - 1) - j;
rotate4(
m [i] [j],
m [r_j] [i],
m [r_i] [r_j],
m [j] [r_i]
);
}
}
}
void fillMatrix(vector<vector<int>>& m) {
int offset = 0;
for (auto &i : m) {
iota(i.begin(), i.end(), offset);
offset += i.size();
}
}
const int size = 8;
vector<vector<int>> matrix (size, vector<int>(size));
fillMatrix(matrix);
rotateMatrix(matrix);
打印
您可以使用以下方法来打印矩阵:
#include <algorithm>
#include <iostream>
#include <iterator>
using std::copy;
using std::cout;
using std::ostream;
using std::ostream_iterator;
using std::vector;
ostream& operator<<(ostream& os, vector<vector<int>>& m) {
for (auto const &i : m) {
copy(i.begin(), i.end(), ostream_iterator<int>(os, " "));
os << "\n";
}
return os;
}
cout << matrix;