Поворот 2D-массива на месте без использования нового массива - лучшее решение C ++?

Question

Один из моих учеников задал мне такую ​​домашнюю работу с массивами C ++.Мне это показалось довольно интересным, поэтому, хотя я решил эту проблему, я хотел поделиться с вами своим решением и узнать другие варианты и мнения.Проблема следующая:

Задача Дана двумерная динамическая квадратичная матрица (массив) A (nxn).Требуется повернуть массив на 90 градусов против часовой стрелки, то есть после поворота поле A [1,1] должно содержать значение A [1, n], а поле A [1, n] должно содержать значениеЭнн]. А также требуется, чтобы при решении этой задачи вы не использовали какой-либо другой массив.

Мое решение Я сказал студенту выполнить следующее (схематично представлять шаги):
Я предложил определить класс, который в качестве его члена будет иметь двумерный массив.И определить операцию, которая будет возвращать ссылку на элемент A [j, n + 1-i] , когда пользователь запросит A [i, j] one.В двух словах я предложил создать оболочку для массива и манипулировать массивом через оболочку.

Answer 1

В Википедии есть статья о транспонировании матрицы на месте .

Рассмотрим:

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

Так что после того, как у вас есть транспонирование, поменяйте местами строки, что вы можете легко сделать на месте.

Answer 2

Вы можете использовать «четырехсторонний обмен» и вложенный цикл с некоторой магией вращения (разработано на бумаге):

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

Теперь вам просто нужно преобразовать это из шаблона в динамическую форму;)

Answer 3

Ниже приведен пример на Java, и его можно легко перенести на C ++. Вращение больших матриц в памяти может потребовать много ресурсов, особенно когда значения матрицы являются сложными объектами. В таких случаях может быть более эффективно пересчитать индексы с функциями, которые перенаправят их на элементы повернутой матрицы без фактического вращения.

public class RotateArray {

public static char arr[][] = { { 'a', 'b', 'c','1' }, { 'd', 'e', 'f','2' }, { 'g', 'h', 'i','3' },{ 'j', 'k', 'l','4' } };
private static int imax = arr.length-1;
private static int jmax = arr[0].length-1;

public static void printArray() {

    for (int i = 0; i <= imax; i++) {
        for (int j = 0; j <= jmax; j++) {
            System.out.print(arr[i][j] + " ");
        }
        System.out.print("\n");
    }
}

public static void printRotatedArray() {
    for (int i = 0; i <= imax; i++) {
        for (int j = 0; j <= jmax; j++) {
            System.out.print(arr[getRotatedI(i,j)][getRotatedJ(i,j)] + " ");
        }
        System.out.print("\n");
    }
}   

public static int getRotatedI(int i,int j){     
    int ii = imax-j;
    return ii;
}

public static int getRotatedJ(int i,int j){
    int jj = i;
    return jj;
}       

public static void main(String[] args) {

    System.out.println("Printing matrix");
    printArray();
    System.out.println("Printing rotated matrix");
    printRotatedArray();
}

}

Выход:

Printing matrix
a b c 1 
d e f 2 
g h i 3 
j k l 4 

Printing rotated matrix
j g d a 
k h e b 
l i f c 
4 3 2 1

Answer 4

Ну, это не C ++, а Java.Извините за это, но вот рекурсивный алгоритм внутри простого массива с поддержкой Matrix:

public void rotateInPlaceRecursive() {
    if( rowCount != colCount ) {
        throw new IllegalStateException("Matrix must be square");
    }
    doRotateInPlaceRecursive(0);
}

public void doRotateInPlaceRecursive(int shrink) {
    if( shrink == rowCount/2 ) {
        return;
    }
    for (int col = shrink; col < colCount-shrink-1; col++) {
        int row = shrink;
        int top     = tab[row][col];
        int left    = tab[rowCount-col-1][row];
        int bottom  = tab[rowCount-row-1][rowCount-col-1];
        int right   = tab[col][rowCount-row-1];

        tab[row][col] = right;
        tab[rowCount-col-1][row] = top;
        tab[rowCount-row-1][rowCount-col-1] = left;
        tab[col][rowCount-row-1] = bottom;

    }
    doRotateInPlaceRecursive(shrink+1);
}

---- TEST

@Test
public void testRotateInPlaceRecursive() {
    // given
    int N = 5;
    Matrix matrix = new Matrix(N, N);

    // when
    int i=0;
    for( int row = 0; row< N; row++ ) {
        for( int col = 0; col< N; col++ ) {
            matrix.set(row,col, i++ );
        }
    }

    // then
    matrix.rotateInPlaceRecursive();
    i = 0;
    for( int row = 0; row< N; row++ ) {
        for( int col = 0; col< N; col++ ) {
            assertEquals(i++,matrix.get(N-col-1,row));
        }
    }
}

Answer 5

O (n ^ 2) время и O (1) пространственный алгоритм (без каких-либо обходных путей и ханкеры!)

Поворот на +90:

Transpose
Reverse each row

Поворот на -90:

Transpose
Reverse each column

Поворот на +180:

Метод 1: Поворот на +90 дважды

Метод 2: перевернуть каждую строку, а затем перевернуть каждый столбец

Поворот на -180:

Метод 1: Поворот на -90 дважды

Метод 2: Перевернуть каждый столбец и затем перевернуть каждую строку

Метод 3: реверс на +180, поскольку они одинаковы