Поверните 2D массив, оперативный, не используя новый массив - лучшее решение C++?
Один из моих студентов спросил меня этот вид домашней работы с массивами C++. Это казалось довольно интересным для меня, таким образом, хотя я решил эту проблему, я хотел совместно использовать свое решение с Вами и знать другого варианты и мнения. Проблема следует:
Проблема Этому дают 2D динамическую квадратичную матрицу (массив) (nxn). Это требуется, чтобы поворачивать массив на 90 градусов против часовой стрелки, то есть после вращения [1,1], поле должно содержать значение [1, n] и [1, n], поле должно содержать значение [n, n]. И также требуется, что при решении этой проблемы Вы не должны использовать никакой другой массив.
Мое решение, которое я сказал студенту, чтобы сделать следующее (представит шаги схематично):
Я предложил определить класс, который, как его участник, будет иметь 2D массив. И определить операцию, которая возвратит ссылку на [j, n+1-i] элемент, когда пользователь запросит [я, j] один. В двух словах я предложил создать обертку для массива и управлять массивом через обертку.
2 ответа
В Википедии есть статья о транспонировании матрицы на месте .
Примите во внимание:
a b c
e f g
x y z
transpose:
a e x
b f y
c g z
rotated 90 deg CCW:
c g z
b f y
a e x
Итак, после того, как вы выполните транспонирование, переверните строки, что вы можете легко сделать на месте.
Вы можете использовать «четырехстороннюю замену» и вложенный цикл с некоторой магией вращения (разработанной на бумаге):
template <typename T>
void swap(T& a, T& b, T& c, T& d)
{
T x(a);
a = b;
b = c;
c = d;
d = x;
}
template <typename T, size_t dim>
void rotate(T (&matrix)[dim][dim])
{
const size_t d = dim-1;
for (size_t y = 0; y < dim/2; ++y)
{
for (size_t x = y; x < d-y; ++x)
{
swap(matrix[y ][x ],
matrix[x ][d-y],
matrix[d-y][d-x],
matrix[d-x][y ]);
}
}
}
Тестовая программа:
template <typename T, size_t dim>
void print(T (&matrix)[dim][dim])
{
for (size_t y = 0; y < dim; ++y)
{
for (size_t x = 0; x < dim; ++x)
{
std::cout << matrix[y][x] << ' ';
}
std::cout << '\n';
}
}
int main()
{
int matrix[4][4] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}};
rotate(matrix);
print(matrix);
}
Вывод:
4 8 12 16
3 7 11 15
2 6 10 14
1 5 9 13
Теперь вам просто нужно преобразовать это из шаблона в динамическую форму;)