Come ruotare una matrice N x N di 90 gradi?

Question

Come ruotare una matrice N x N di 90 gradi. Voglio che sia al suo posto?

Answer 1

for(int i=0; i<n/2; i++) 
    for(int j=0; j<(n+1)/2; j++) 
     cyclic_roll(m[i][j], m[n-1-j][i], m[n-1-i][n-1-j], m[j][n-1-i]); 


void cyclic_roll(int &a, int &b, int &c, int &d) 
{ 
    int temp = a; 
    a = b; 
    b = c; 
    c = d; 
    d = temp; 
} 

Nota non ho ancora testato questo , appena compoosed ora sul posto. Si prega di testare prima di fare qualsiasi cosa con esso.

Answer 2

È possibile creare un secondo array e quindi copiare il primo nel secondo leggendo row-major nel primo e scrivendo column-major nel secondo.

Così si sarebbe copiare:

1 2 3 
4 5 6 
7 8 9 

e si dovrebbe leggere la prima fila poi scrivere il backup di partenza come:

3 
2 
1 

Answer 3

ecco la mia soluzione: (ruotare pi/2 in senso orario)

1. fare la trasposta della matrice, (come matrice trasposta)

2. invertire gli elementi di ogni riga

   cons int row = 10; 
   cons int col = 10; 
   //transpose 
   for(int r = 0; r < row; r++) { 
       for(int c = r; c < col; c++) { 
       swap(Array[r][c], Array[c][r]); 
       } 
   } 
   //reverse elements on row order 
   for(int r = 0; r < row; r++) { 
       for(int c =0; c < col/2; c++) { 
        swap(Array[r][c], Array[r][col-c-1]) 
       } 
   } 
   

se ruotare pi/2 in senso antiorario

1. trasporre la matrice

2. invertire gli elementi su ordinazione colonna

mai testare il codice! ogni suggerimento sarebbe apprezzato!

Answer 4

Un programma C completo che illustra il mio approccio. Essenzialmente è un algo ricorsivo. Ad ogni ricorsione ruoti lo strato esterno. Interrompi quando la tua matrice è 1x1 o 0x0.

#include <stdio.h> 

int matrix[4][4] = { 
    {11, 12, 13, 14}, 
    {21, 22, 23, 24}, 
    {31, 32, 33, 34}, 
    {41, 42, 43, 44} 
}; 

void print_matrix(int n) 
{ 
    for (int i = 0; i < n; i++) { 
     for (int j = 0; j < n; j++) { 
     printf(" %d ", matrix[i][j]); 
     } 
     printf("\n"); 
    } 
} 

int *get(int offset, int x, int y) 
{ 
    return &matrix[offset + x][offset + y]; 
} 

void transpose(int offset, int n) 
{ 
    if (n > 1) { 
     for (int i = 0; i < n - 1; i++) { 
     int *val1 = get(offset, 0, i); 
     int *val2 = get(offset, i, n - 1); 
     int *val3 = get(offset, n - 1, n - 1 - i); 
     int *val4 = get(offset, n - 1 - i, 0); 

     int temp = *val1; 
     *val1 = *val4; 
     *val4 = *val3; 
     *val3 = *val2; 
     *val2 = temp; 
     } 

     transpose(offset + 1, n - 2); 
    } 
} 

main(int argc, char *argv[]) 
{ 
    print_matrix(4); 
    transpose(0, 4); 
    print_matrix(4); 
    return 0; 
} 

Answer 5

//Java version, fully tested 

public class Rotate90degree { 


     public static void reverseElementsRowWise(int[][] matrix) { 
      int n = matrix.length; 
      for(int i = 0; i < n; ++i) { 
       for(int j = 0; j < n/2; ++j) { 
        int temp = matrix[i][n - j - 1]; 
        matrix[i][n - j - 1] = matrix[i][j]; 
        matrix[i][j] = temp; 
       } 
      } 
     } 

     public static void transpose(int[][] matrix) { 
      int n = matrix.length; 
      for(int i = 0; i < n; ++i) { 
       for(int j = i + 1; j < n; ++j) { 
        int temp = matrix[i][j]; 
        matrix[i][j] = matrix[j][i]; 
        matrix[j][i] = temp; 
       } 
      } 
     } 

     public static void rotate90(int[][] matrix) { 
      transpose(matrix); 
      reverseElementsRowWise(matrix); 
     } 

     public static void print(int[][] matrix) { 
      int n = matrix.length; 
      for(int i = 0; i < n; ++i) { 
       for(int j = 0; j < n; ++j) { 
        System.out.print(matrix[i][j]); 
        System.out.print(' '); 
       } 
       System.out.println(); 
      } 
     } 

     public static void main(String[] args) { 
      int[][] matrix = { 
        {1, 2, 3, 4}, 
        {5, 6, 7, 8}, 
        {9, 10, 11, 12}, 
        {13, 14, 15, 16}}; 
      System.out.println("before"); 
      print(matrix); 
      rotate90(matrix); 
      System.out.println("after"); 
      print(matrix); 
     } 
}