Obracanie macierzy dwuwymiarowej o 90 stopni

Question

Studiuję ten fragment kodu podczas obracania macierzy NxN; Wiele razy śledziłem program i trochę rozumiem, jak zachodzi faktyczna rotacja. Obraca on najpierw rogi i elementy za rogami w kierunku zgodnym z ruchem wskazówek zegara. Po prostu nie rozumiem kilku linii, a kod nadal nie jest "napędzany domem" w moim mózgu, że tak powiem. Proszę pomóż. Obracam go o 90 stopni, biorąc pod uwagę macierz 4x4 jako przykład śledzenia.

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

staje

[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

Łatwiej zrozumieć algorytm tak, jeśli narysować schemat, więc zrobiłem szybki pic w farbie, aby wykazać dla macierzy 5x5: D

Zewnętrzna pętla for(int layer=0; layer < n/2; ++layer) iteruje po warstwach od zewnątrz do wnętrza. Warstwa zewnętrzna (warstwa 0) jest przedstawiona kolorowymi elementami. Każda warstwa jest faktycznie kwadratem elementów wymagających obrotu. Dla n = 5, warstwa przyjmie wartości od 0 do 1, ponieważ są 2 warstwy, ponieważ możemy zignorować środkowy element/warstwę, na którą nie ma wpływu obrót. najpierw i ostatni odnoszą się do pierwszego i ostatniego wiersza/kolumny elementów dla warstwy; na przykład Warstwa 0 ma elementy z wiersz/kolumna Pierwszy = 0 do ostatni = 4 i warstwy 1 z wiersz/kolumna 1 do 3.

Następnie dla każdej warstwy/kwadrat, wewnętrzna for(int i=first; i<last;++i) pętli obraca się obracając 4 elementy w każdej iteracji. Przesunięcie przedstawia odległość wzdłuż boków kwadratu. W naszym 5x5 poniżej najpierw obracamy czerwone elementy (offset = 0), następnie żółty (offset = 1), a następnie zielony i niebieski. Strzałki 1-5 demonstrują rotację 4-elementową dla czerwonych elementów, a 6+ dla pozostałych, które są wykonywane w ten sam sposób. Zwróć uwagę, że obrót w 4 elementach jest w istocie 5-kołowym zamiennikiem kołowym, a pierwsze zadanie tymczasowo odkłada element. Komentarz //save the top left of the matrix dla tego przypisania jest mylący, ponieważ matrix [first] [i] niekoniecznie jest lewą górną częścią matrycy lub nawet warstwą dla tej kwestii. Zwróć też uwagę, że indeksy wiersza/kolumny obracanych elementów są czasami proporcjonalne do przesunięcia i czasami proporcjonalne do jego odwrotności, , ostatniej korekcji.

Poruszamy się wzdłuż boków warstwy zewnętrznej (w pierwszym rzędzie oznaczamy najpierw = 0 i ostatni = 4), a następnie przesuwamy się na warstwę wewnętrzną (pierwsza = 1 i ostatnia = 3) i robimy to samo. W końcu dotarliśmy do centrum i skończyliśmy.

Answer 2

to za sobą WTF. Najprostszym sposobem obracanie matrycy zamiast jest

• pierwszy transpozycję macierzy (swap M [i, j] o M [j, j])
• następnie wymiany K [i, j] o M [i, nColumns - j]

Gdy macierzami są kolumny-główne, druga operacja polega na zamianie kolumn, a więc ma dobre właściwości lokalizacji danych. Jeśli macierz ma wiersz główny, to najpierw wiersze permute, a następnie transponuj.

Answer 3

Oto rekurencyjny sposób rozwiązania tego:

// obracania tablicy 2 d (MxN) o 90 stopni

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