Ruota un array 2D sul posto senza utilizzare un nuovo array: la migliore soluzione C++?

Question

Uno dei miei studenti mi ha chiesto questo tipo di compiti con gli array C++. Mi è sembrato piuttosto interessante, quindi, sebbene abbia risolto questo problema, ho voluto condividere la mia soluzione con te e conoscere altre varianti e opinioni. Il problema è il seguente:

Problema Viene fornita una matrice quadratica dinamica dinamica (matrice) A (nxn). È necessario ruotare l'array di 90 gradi in senso antiorario, vale a dire dopo che il campo A [1,1] di rotazione deve contenere il valore di A [1, n] e il campo A [1, n] deve contenere il valore di A [n, n]. E inoltre è necessario che mentre si risolve questo problema non si debba usare nessun altro array.

La mia soluzione Ho detto allo studente di fare quanto segue (rappresenterà passi schematicamente):
ho suggerito di definire una classe che, come il suo membro, avrà la matrice 2D. E per definire un'operazione che restituirà riferimento su A [j, n + 1-i] elemento quando l'utente richiederà A [i, j] uno. In due parole ho suggerito di creare un wrapper per l'array e di manipolarlo per mezzo del wrapper.

Answer 1

Wikipedia ha un articolo su in-place matrix transposition.

considerare:

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 

Così dopo avete la trasposizione, invertire le righe, che si può fare sul posto facilmente.

Answer 2

È possibile utilizzare un "quattro vie-swap" e un ciclo nidificato con qualche magia di rotazione (elaborato su carta): programma

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

prova:

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

uscita:

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

Ora dovete solo convertire che dal modello di forma di dinamica-forma;)

012.351.641.061.

Answer 3

Bene, quello non è C++ ma Java. Ci scusiamo per questo, ma qui è un algoritmo ricorsivo all'interno di un semplice array sostenuta 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) tempo e O (1) algoritmo di spazio (senza soluzioni alternative e roba fasulla!)

Ruota di +90:

Transpose 
Reverse each row 

Ruota di -90:

Transpose 
Reverse each column 

Ruota di 180:

Metodo 1: Ruota di +90 doppio

Metodo 2: Invertire ogni riga e invertire ogni colonna

Ruota di -180:

Metodo 1: Ruota di -90 volte

Metodo 2: inversione ogni colonna e poi invertire ogni riga

Metodo 3: inversione da +180 come sono stessi

Answer 5

Sotto l'esempio è in Java e può essere facilmente adottato in C++. La rotazione di matrici di grandi dimensioni in memoria potrebbe consumare molte risorse, specialmente quando i valori della matrice sono oggetti complessi. In questi casi potrebbe essere più efficiente ricalcolare gli indici con funzioni che li reindirizzino agli elementi della matrice ruotata senza rotazione effettiva.

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

} 

uscita:

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