Алгоритм поворота динамического массива без доп памяти?

Question

[avion]

Здравствуйте, какой существует алгоритм для поворота матрицы разной размерности на 90 по и против часовой стрелки. С доп памятью задача тривиальна, но вот без, так еще и разной размерности ...
Имеется динамический массив размерности m x n.
Данный код, работает для размерности n x n:

int tmp;
 for(int i=0;i<n/2;i++)
 {
 for(int j=i;j<n-1-i;j++)
 {
 tmp = matr[i][j];
 matr[i][j] = matr[n-j-1][i];
 matr[n-j-1][i] = matr[n-i-1][n-j-1];
 matr[n-i-1][n-j-1] = matr[j][n-i-1];
 matr[j][n-i-1] = tmp;
 }
 }
}

Как можно реализовать, поворот динамического массива (матрица), без доп памяти?

Comments

[jcmvbkbc]

Ты уверен, что хочешь именно поворачивать матрицу в памяти, вместо того чтобы просто преобразовывать индексы?

[Lynn «Кофеман»]

А что такое поворот неквадратной матрицы?
Как была выделена память изначально?

Answer 1

[xmoonlight]

Свап ячеек через сумму и вычитание.

Answer 2

[jcmvbkbc]

Как можно реализовать, поворот динамического массива (матрица), без доп памяти?

Как-то так:

#include <stddef.h>
#include <stdio.h>

typedef int T;

void rotate(T *p, size_t m, size_t n, size_t (*turn)(size_t m, size_t n, size_t idx))
{
        size_t i, j, k;

        for (i = 0; i < m * n; ++i) {
                T tmp0, tmp1;

                for (j = 0; j < i; ++j) {
                        for (k = turn(m, n, j); k != i && k != j; k = turn(m, n, k)) {
                        }
                        if (k == i)
                                break;
                }
                if (j < i)
                        continue;

                tmp0 = p[i];
                for (j = turn(m, n, i); ; j = turn(m, n, j)) {
                        tmp1 = p[j];
                        p[j] = tmp0;
                        tmp0 = tmp1;
                        if (j == i)
                                break;
                }
        }
}

void dump(size_t m, size_t n, T p[m][n])
{
        size_t i, j;

        for (i = 0; i < m; ++i)
                for (j = 0; j < n; ++j)
                        printf("%d%s", p[i][j], j == n - 1 ? "\n" : ", ");
}

size_t turn_ccw(size_t m, size_t n, size_t idx)
{
        return (n - 1 - idx % n) * m + (idx / n);
}

size_t turn_cw(size_t m, size_t n, size_t idx)
{
        return (idx % n) * m + m - 1 - (idx / n);
}

#define M 5
#define N 7

int main()
{
        size_t i, j;
        T a[M][N];

        for (i = 0; i < M; ++i)
                for (j = 0; j < N; ++j)
                        a[i][j] = i * N + j;

        rotate(&a[0][0], M, N, turn_ccw);
        dump(N, M, (T (*)[M])&a[0][0]);
        printf("\n");
        rotate(&a[0][0], N, M, turn_cw);
        dump(M, N, (T (*)[N])&a[0][0]);
}

turn преобразует линейный индекс элемента из оригинального массива в индекс элемента в повёрнутом массиве.
Цикл по i переставляет цепочки элементов отображающихся друг в друга с началом в элементе i. Первый цикл по j проверяет, не был ли элемент i уже переставлен в составе более ранней цепочки. Второй цикл по j переставляет одну цепочку.

Answer 3

[maaGames]

В первую очередь рассмотреть вариант сохранения флага "транспонированная матрица" и учёт этого флага в алгоритмах. Причём, это ускорит работу ДВАЖДЫ, т.к. обход по столбцу транспонированной матрицы физически оказывается обходом по строке, что положительно сказывается на кэшировании данных матрицы.

Answer 4

[mayton2019]

Можно эту прямоугольную "колбасу" вообще не поворачивать. А хранить вектор повернутости. И перегрузить оператор индекса чтобы доступ вел себя по правилам аффинных преобразований.