Эта проблема заняла у меня довольно много времени, но при правильном подходе она очень проста.
Обратите внимание, что это работает только для квадратной матрицы . Прямоугольник потребует от вас использовать другой алгоритм (транспонировать и перевернуть). Если вы хотите сделать это на месте, может потребоваться временное изменение размера массива.
Упрощение задачи
Рассмотрим следующую матрицу:
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.
Вращающиеся углы
Чтобы повернуть углы, необходимо определить все углы в терминах первого угла:
- 1-й угол будет
(i, j)
- 2-й угол будет
(SIZE - j, i)
- 3-й угол будет
(SIZE - i, SIZE - j)
- 4-й угол будет
(j, SIZE - i)
Обратите внимание, что массивы основаны на 0, поэтому SIZE также должен быть основан на 0.
Теперь, когда вы поняли идею вращающихся углов, мы расширим идею «вращающихся углов» до «вращающихся квадрантов». Тот же принцип сохраняется.
Код
Вам нужно будет убедиться, что номер не перезаписан. Это означает, что вам нужно будет вращать 4 числа одновременно.
#include <algorithm>
#include <numeric>
#include <vector>
using std::iota;
using std::swap;
using std::vector;
// Rotates 4 numbers.
// e.g: 1, 2, 3, 4 becomes 4, 1, 2, 3
// int& means numbers are passed by reference, not copy.
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();
// NOTE: i and j from 0 to n/2 is a quadrant
for (int i = 0; i < n/2; i++) {
// NOTE : here + 1 is added to make it work when n is odd
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();
}
}
// Usage:
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;
}
// Usage
cout << matrix;