Rotar una matriz bidimensional en 90 grados

Question

Estoy estudiando esta pieza de código al rotar una matriz NxN; He trazado el programa innumerables veces, y entiendo cómo ocurre la rotación real. Básicamente gira las esquinas primero y los elementos después de las esquinas en el sentido de las agujas del reloj. Simplemente no entiendo un par de líneas, y el código todavía no está "dirigido a casa" en mi cerebro, por así decirlo. Por favor ayuda. Lo estoy girando 90 grados, con una matriz de 4x4 como mi ejemplo de rastreo.

[1][2][3][4] 
[5][6][7][8] 
[9][0][1][2] 
[3][4][5][6] 

convierte

[3][9][5][1] 
[4][0][6][2] 
[5][1][7][3] 
[6][2][8][4] 

---

public static void rotate(int[][] matrix, int n){ 
    for(int layer=0; layer < n/2; ++layer) { 
    int first=layer; //It moves from the outside in. 
    int last=n-1-layer; //<--This I do not understand 
    for(int i=first; i<last;++i){ 
     int offset=i-first; //<--A bit confusing for me 

     //save the top left of the matrix 
     int top = matrix[first][i]; 

     //shift left to top; 
     matrix[first][i]=matrix[last-offset][first]; 
     /*I understand that it needs 
     last-offset so that it will go up the column in the matrix, 
     and first signifies it's in the first column*/ 

     //shift bottom to left 
     matrix[last-offset][first]=matrix[last][last-offset]; 
     /*I understand that it needs 
     last-offset so that the number decreases and it may go up the column (first 
     last-offset) and left (latter). */ 

     //shift right to bottom 
     matrix[last][last-offset]=matrix[i][last]; 
     /*I understand that it i so that in the next iteration, it moves down 
     the column*/   



     //rightmost top corner 
     matrix[i][last]=top; 
     } 
    } 

} 

Answer 1

Es más fácil de entender un algoritmo de este tipo si se dibuja un diagrama, así que hice una foto rápida en Paint para demostrar de una matriz 5x5: D

El ciclo externo for(int layer=0; layer < n/2; ++layer) itera sobre las capas de afuera hacia adentro. La capa externa (capa 0) está representada por elementos coloreados. Cada capa es efectivamente un cuadrado de elementos que requieren rotación. Para n = 5, , la capa tomará valores de 0 a 1, ya que hay 2 capas ya que podemos ignorar el elemento/capa central que no se ve afectado por la rotación. primero y último consulte la primera y la última filas/columnas de elementos para una capa; p.ej. capa 0 tiene elementos de fila/columna primera = 0-última = 4 y la capa 1 de la fila/columna de 1 a 3.

Luego, para cada capa/cuadrado, el interior for(int i=first; i<last;++i) bucle hace girar mediante la rotación de 4 elementos en cada iteración. Offset representa la distancia a lo largo de los lados del cuadrado en que nos encontramos. Para nuestro 5x5 abajo, primero rotamos los elementos rojos (desplazamiento = 0), luego amarillo (desplazamiento = 1), luego verde y azul. Las flechas 1-5 demuestran la rotación de 4 elementos para los elementos rojos, y 6+ para el resto, que se realizan de la misma manera. Observe cómo la rotación de 4 elementos es esencialmente un intercambio circular de 5 tareas con la primera asignación temporalmente dejando de lado un elemento. El comentario //save the top left of the matrix para esta tarea es engañoso ya que la matriz [primera] [i] no es necesariamente la parte superior izquierda de la matriz o incluso la capa para ese asunto. Además, tenga en cuenta que los índices de fila/columna de los elementos que se rotan a veces son proporcionales a offset y a veces son proporcionales a su inversa, last - offset.

Nos movemos a los lados de la capa externa (delineados por primero = 0 y dura = 4) de esta manera, luego avanzamos hacia la capa interna (primero = 1 y dura = 3) y hacemos lo mismo allí. Finalmente, llegamos al centro y terminamos.

Answer 2

Este disparador un WTF. La forma más fácil para girar una matriz en lugar es por

• primera transposición de la matriz (de intercambio M [i, j] con M [j, i])
• entonces el intercambio de M [i, j] con M [i, nColumns - j]

Cuando las matrices son columnas principales, la segunda operación es el intercambio de columnas y, por lo tanto, tiene buenas propiedades de localidad de datos. Si la matriz es fila mayor, entonces primero permute las filas, y luego transpórtela.

Answer 3

Aquí es una forma recursiva de resolver esto:

// girar una matriz de 2 D (MXN) en 90 grados

public void rotateArray(int[][] inputArray) { 
    System.out.println("Input Array: "); 
    print2D(inputArray); 
    rotateArray(inputArray, 0, 0, inputArray.length - 1, 
      inputArray[0].length - 1); 
    System.out.println("\n\nOutput Array: "); 
    print2D(inputArray); 

} 

public void rotateArray(int[][] inputArray, int currentRow, 
     int currentColumn, int lastRow, int lastColumn) { 

    // condition to come out of recursion. 
    // if all rows are covered or all columns are covered (all layers 
    // covered) 
    if (currentRow >= lastRow || currentColumn >= lastColumn) 
     return; 
    // rotating the corner elements first 
    int top = inputArray[currentRow][currentColumn]; 
    inputArray[currentRow][currentColumn] = inputArray[lastRow][currentColumn]; 
    inputArray[lastRow][currentColumn] = inputArray[lastRow][lastColumn]; 
    inputArray[lastRow][lastColumn] = inputArray[currentRow][lastColumn]; 
    inputArray[currentRow][lastColumn] = top; 

    // clockwise rotation of remaining elements in the current layer 
    for (int i = currentColumn + 1; i < lastColumn; i++) { 
     int temp = inputArray[currentRow][i]; 
     inputArray[currentRow][i] = inputArray[lastRow - i][currentColumn]; 
     inputArray[lastRow - i][currentColumn] = inputArray[lastRow][lastColumn 
       - i]; 
     inputArray[lastRow][lastColumn - i] = inputArray[currentRow + i][lastColumn]; 
     inputArray[currentRow + i][lastColumn] = temp; 
    } 

    // call recursion on remaining layers 
    rotateArray(inputArray, ++currentRow, ++currentColumn, --lastRow, 
      --lastColumn); 
}