2

Tenho um array bidimensional, de tamanho M x N, que armazena tiles de um mapa, no seguinte formato:

[1, 2, 3],

[4, 5, 6],

[7, 8, 9],

[10, 11, 12]

E quero rotacionar em 90º (ex: girar o mapa de forma que o Norte fique no Leste). O exemplo rotacionado ficaria assim:

[10, 7, 4, 1],

[11, 8, 5, 2],

[12, 9, 6, 3]

Note que a matriz mudou de tamanho: foi para N x M após a rotação. Isso é similar ao que acontece ao rotacionar certas peças do jogo Tetris: quanto mais alongada (alta) ela for, mais larga ficará ao ser rotacionada.

Como fazer para rotacionar este tipo de array bidimensional em Java?

1 Resposta 1

4

No exemplo, a matriz de 4x3 pode ser declarada da seguinte forma:

 int[][] a1 = new int[][]{   new int[]{1,2,3},
                             new int[]{4,5,6},
                             new int[]{7,8,9},
                             new int[]{10,11,12}};

Ou seja é um array de arrays de int. Abaixo estão descritos os códigos para rotacionar arrays de duas dimensões no sentido horário e anti-horário, respectivamente:

public static int[][] rotacionarMatrizHorario(int[][] matriz) {
    int largura = matriz.length;
    int altura = matriz[0].length;
    int[][] ret = new int[altura][largura];
    for (int i=0; i<altura; i++) {
        for (int j=0; j<largura; j++) {
            ret[i][j] = matriz[largura - j - 1][i];
        }
     }
    return ret;
}


public static int[][] rotacionarMatrizAntiHorario(int[][] matriz) {
    int largura = matriz.length;
    int altura = matriz[0].length;   
    int[][] ret = new int[altura][largura];
    for (int i=0; i<altura; i++) {
        for (int j=0; j<largura; j++) {
            ret[i][j] = matriz[j][altura - i - 1];
        }
    }
    return ret;
}

Para virar uma matriz "de cabeça para baixo", basta rotacioná-la duas vezes em 90°, totalizando assim 180°:

[12, 11, 10],
[9, 8, 7],
[6, 5, 4],
[3, 2, 1]

Ao girar a matriz original em 90º três vezes, ou seja, em 270°, o resultado é o mesmo que girar a matriz em 90° no sentido anti-horário. O resultado será esse:

[3, 6, 9, 12],
[2, 5, 8, 11],
[1, 4, 7, 10]

Essa é a implementação mais simples: os métodos possuem uma complexidade da ordem de O(N²), onde N é o tamanho da matriz, ou mais precisamente O(M*N), onde M é a altura e N a largura da matriz.

Dependendo da aplicação, podem ser implementadas maneiras mais eficientes de rotacionar a matriz. É possível diminuir a complexidade para O(N)*log(N), ou até mais, se forem considerados tratamentos especiais no caso de matrizes esparsas, ou mesmo otimizações de acordo com a arquitetura do computador que fará as rotações.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .