Last active
November 28, 2016 08:15
-
-
Save vromero/e363d99bcf57d4725417dc7434f794e4 to your computer and use it in GitHub Desktop.
Traverse matrix in spiral form. My personal approach.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.company; | |
public class Main { | |
/** | |
* This algorithm will divide the matrix into layers and portions. Layers are taken from the outside to the inside. | |
* i.e: | |
* <pre> | |
* 1 1 1 1 1 | |
* 1 2 2 2 1 | |
* 1 2 2 2 1 | |
* 1 1 1 1 1 | |
* </pre> | |
* | |
* Then the portions will be divided as follows: | |
* <pre> | |
* 1 1 1 1 2 | |
* 4 1 1 2 2 | |
* 4 4 3 3 2 | |
* 4 3 3 3 3 | |
* </pre> | |
* | |
* Each of the portions will have a different movement. The first to portions will have the exact inverse movement | |
* than the last two portions. | |
*/ | |
void rotate(int[][] matrix) { | |
// Divide into layers, starting from the outside to the inside | |
for (int l = 0; l < Math.max(matrix.length, matrix[0].length) / 2; l++) { | |
// Divide each of the layers into portions | |
// A portion contains a series of cells that will require the same movement | |
int horizontalPortionWidth = matrix[0].length - 1 - (l * 2); | |
int verticalPortionHeight = matrix.length - 1 - (l * 2); | |
// The last cell count to visit, in base 1 | |
int lastCell = horizontalPortionWidth * 2 + verticalPortionHeight * 2; | |
// The initial position of the layer | |
int positionX = l, positionY = l; | |
// Now visit each of the cells of the layer in spiral order | |
for (int c = 0; c < lastCell; c++) { | |
System.out.println(matrix[positionY][positionX]); | |
// Calculate the current portion | |
int currentPortion = ((c % (horizontalPortionWidth + verticalPortionHeight)) | |
/ horizontalPortionWidth) + (2 * (c / (horizontalPortionWidth + verticalPortionHeight))); | |
// The last two portions, have the same movement than the first two but inverted 1 -> -1, -1 -> 1 | |
int inverter = currentPortion > 1 ? -1 : 1; | |
// Calculate the movement given the current portion | |
int absoluteYDelta = (currentPortion % 2) * inverter; | |
int absoluteXDelta = (1 - currentPortion % 2) * inverter; | |
positionY += absoluteYDelta; | |
positionX += absoluteXDelta; | |
} | |
} | |
} | |
public static void main(String[] args) { | |
Main rotateMatrix = new Main(); | |
int[][] matrix = { | |
{1, 2, 3, 4}, | |
{10, 11, 12, 5}, | |
{ 9, 8, 7, 6}}; | |
rotateMatrix.rotate(matrix); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment