Gire una matriz 2D in situ sin utilizar una nueva matriz: ¿la mejor solución de C++?

Question

Uno de mis alumnos me pidió este tipo de tarea con arreglos en C++. Me pareció bastante interesante, así que, aunque he resuelto este problema, quería compartir mi solución con usted y conocer otras variantes y opiniones. El problema es el siguiente:

Problema Se administra una matriz cuadrática (array) Una dinámica 2D (nxn). Se requiere girar la matriz 90 grados en el sentido contrario al de las agujas del reloj, es decir, después de la rotación Un campo [1,1] debe contener el valor del campo A [1, n] y A [1, n] debe contener el valor de Ana]. Y también se requiere que al resolver este problema no use otra matriz.

Mi solución Me han dicho que el estudiante para hacer lo siguiente (se representan esquemáticamente los pasos):
he sugerido para definir una clase que, como su miembro, tendrá la matriz 2D. Y para definir una operación que devolverá la referencia en Un elemento [j, n + 1-i] cuando el usuario solicite A [i, j] uno. En dos palabras, he sugerido crear una envoltura para la matriz y manipularla mediante una matriz a través de la envoltura.

Answer 1

Wikipedia tiene un artículo en in-place matrix transposition.

considerar:

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 

Así que después de tener la transpuesta, revertir las filas, que se puede hacer en lugar fácilmente.

Answer 2

Puede utilizar un "cuatro vías de intercambio" y un bucle anidado con un poco de magia de rotación (elaborado en papel): programa de

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 ]); 
     } 
    } 
} 

prueba:

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); 
} 

Salida:

4 8 12 16 
3 7 11 15 
2 6 10 14 
1 5 9 13 

Ahora sólo tiene que convertir que a partir de plantilla de forma de forma dinámica;)

Answer 3

Bueno, eso no es C++ sino Java. Lo siento por esto, pero aquí es un algoritmo recursivo dentro de una matriz sencilla respaldado 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 4

O (n^2) tiempo y O (1) algoritmo espacio (sin ningún tipo de soluciones y cosas pañuelo!)

Girar 90:

Transpose 
Reverse each row 

Girar -90:

Transpose 
Reverse each column 

Girar 180:

Método 1: Girar por 90 dos veces

Método 2: invierta cada fila y luego invierta cada columna

Girar -180:

Método 1: Girar -90 dos veces

Método 2: Reverse cada columna y luego invertir cada fila

Método 3: Reverse por 180, ya que son mismo

Answer 5

El siguiente ejemplo está en Java y se puede adoptar fácilmente en C++. Rotar matrices grandes en la memoria puede consumir muchos recursos, especialmente cuando los valores de la matriz son objetos complejos. En tales casos, podría ser más eficiente recalcular los índices con funciones que los redireccionarían a elementos de matriz girada sin rotación real.

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(); 
} 

} 

Salida:

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