Comment faire pivoter une matrice N x N de 90 degrés?

Question

Comment faire pivoter une matrice N x N de 90 degrés. Je veux que ce soit inplace?

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

Remarque Je n'ai pas testé , vient de composer maintenant sur place. S'il vous plaît tester avant de faire quoi que ce soit avec.

Answer 2

Vous pouvez créer un deuxième tableau, puis copier le premier dans le second en lisant row-major dans le premier et en écrivant column-major au second.

Vous copieriez:

1 2 3 
4 5 6 
7 8 9 

et vous lisez la première ligne, puis écrire de nouveau démarrage comme:

3 
2 
1 

Answer 3

voici ma solution: (tourner pi/2 dans le sens horaire)

1. faire la transposée de la matrice, (comme matrice transposée)

2. inverser les éléments de chaque rangée

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

si tourner pi/2 dans le sens antihoraire

1. transposer le tableau

2. inverser les éléments sur l'ordre des colonnes

jamais tester le code! toute suggestion serait appréciée!

Answer 4

Un programme C complet qui illustre ma démarche. Essentiellement, c'est l'algo récursif. À chaque récursion, vous faites pivoter la couche externe. Arrêtez lorsque votre matrice est 1x1 ou 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); 
     } 
}