Geek asks and answers

How to change the directions and starting points of this spiral matrix traversal?

I have a code ( following this example ) to traverse the matrix, starting from the top left corner and clockwise. I want to make three new methods based on this:

  • One that starts from the top left corner and goes counterclockwise
  • One that starts in the middle and goes clockwise
  • One that starts in the middle and goes counterclockwise

What do I need to change for each of them? I tried changing the counter increments and changing the start / end row / columns without success.

public static void traverseSpiral(int[][] matrix) {

    if(matrix.length == 0|| matrix[0].length == 0) {
        return;
    }

    StringBuffer stringBuffer = new StringBuffer();
    int counter = matrix.length * matrix[0].length;
    int startRow = 0;
    int endRow = matrix.length-1;
    int startCol = 0;
    int endCol = matrix[0].length-1;
    boolean moveCol = true;
    boolean leftToRight = true;
    boolean upDown = true;

    while(counter>0) {
        if(moveCol) {
            if(leftToRight) {

            /* printing entire row left to right */
                for(int i = startCol; i <= endCol ; i++){
                    stringBuffer.append(matrix[startRow][i]);
                    counter--;
                }
                leftToRight = false;
                moveCol = false;
                startRow++;
            }
            else{

            /* printing entire row right to left */
                for(int i = endCol ; i >= startCol ; i--){
                    stringBuffer.append(matrix[endRow][i]);
                    counter--;
                }
                leftToRight = true;
                moveCol = false;
                endRow--;
            }
        }
        else
        {
            if(upDown){

            /* printing column up down */
                for(int i = startRow ; i <= endRow ; i++){
                    stringBuffer.append(matrix[i][endCol]);
                    counter--;
                }
                upDown = false;
                moveCol = true;
                endCol--;
            }
            else
            {

            /* printing entire col down up */
                for(int i = endRow ; i >= startRow ; i--){
                    stringBuffer.append(matrix[i][startCol]);
                    counter--;
                }
                upDown = true;
                moveCol = true;
                startCol++;
            }
        }
    }
    System.out.println(stringBuffer.toString());
}
+3
source share
3 answers

, , ( ).

, , . . . , , . ( ) .

, . , , , , , .

, . , ( , , ). .

, 5 :

// A method that will handle the traversal of the spiral.
public static String clockwise(int[][] matrix);

// Responsible for printing a column from bottom to top.
public static String up(int[][] matrix, int first, int last);

// Responsible for printing a column from top to bottom.
public static String down(int[][] matrix, int first, int last);

// Responsible for printing a column from right to left.
public static String left(int[][] matrix, int first, int last);

// Responsible for printing a column from left to right.
public static String right(int[][] matrix, int first, int last);

, , up(matrix, first, last), down(matrix, first, last), left(matrix, first, last) right(matrix, first, last), :

Clockwise          = right, down, left, up;
Counter-Clockwise  = down, right, up, left;

divide-and-conquer. 3x3 2x2 , , .

, , " " . , , , , . GitHub Gist .

. - - . .

+2

:

  • ,

  • ,

  • ,

( )

3x3

+---+---+---+  
|   |   |   |
+---+---+---+  
|   |   |   |
+---+---+---+  
|   |   |   |
+---+---+---+

,

SR=0, ER=2, SC=0, EC=2

(SR: startRow, ER: endRow, SC: startCol, EC: endCol)

SC->EC 
SR++   (=>SR=1)
SR->ER 
EC--   (=>EC=1)
EC->SC 
ER--   (=>ER=1)
ER->SR
SC++   (=>SC=1)
SC->EC
-> finish with (SR=1,ER=1,SC=1,EC=1)

, .

SR=1, ER=1, SC=1, EC=1
EC->SC
SC--
SR->ER
ER++
SC->EC
EC++
ER->SR
SR--
EC->SC
-> finish with (SR=0,ER=2,SC=0,EC=2)

, SR, ER, SC, EC, , . , , startCol endCol. .

,

if(leftToRight) {

/* printing entire row left to right */
    for(int i = startCol; i <= endCol ; i++){
        stringBuffer.append(matrix[startRow][i]);
        counter--;
    }
    leftToRight = false;
    moveCol = false;
    startRow++;
} 


if (leftToRight) {

    /* printing entire row left to right */
    for (int i = startCol; i <= endCol; i++) {
        stringBuffer.append(matrix[endRow][i]);
        counter--;
    }
    leftToRight = false;
    moveCol = false;
    endCol++;
}

, # # , , (moveCol, leftRight, upDown). , #, # , .

+---+---+---+---+  
|   |   |   |   |
+---+---+---+---+  
|   | P |   |   |
+---+---+---+---+  
|   |   |   |   |
+---+---+---+---+  
|   |   |   |   |
+---+---+---+---+

, 4x4, P (1,1) (startRow = (4-1)/2, startCol = (4-1)/2), (upDown = true, leftRight = true, moveCol = false)

if (leftToRight) {

    /* printing entire row left to right */
    for (int i = startCol; i <= endCol; i++) {
        stringBuffer.append(matrix[startRow][i]);
        counter--;
    }
    leftToRight = false;
    moveCol = false;
    endCol++;
}
+1

, . :

class Region  {
    int left, right, top, bottom;
    Region(int _left, int _right, int _top, int_bottom) {
        left=_left;  right=_right;  top=_top;  bottom=_bottom; 
    }
    boolean isEmpty() { return (left>right || top>bottom); }
    boolean isSingleElement() { return (left==right && top==bottom); }
}

List<Coordinate> traverseClockWise(Region r) {
    List<Coordinate> l = new List<Coordinate>();
    if (r.isEmpty()) {
        return l; 
    }
    if (r.isSingleElement()) {
        l.add(new Coordinate(r.left, r.top));
        return l; 
    }

    for (int i=r.left; i<r.right; i++) {
        l.add(new Coordinate(i, r.top));
    }
    for (int i=r.top; i<r.bottom; i++) {
        l.add(new Coordinate(r.right, i));
    }
    for (int i=r.right; i>r.left; i--) {
        l.add(new Coordinate(i, r.bottom));
    }
    for (int i=r.bottom; i>r.top; i--) {
        l.add(new Coordinate(r.left, i));
    }

    l.addAll(traverseClockWise(new Region(r.left+1, r.right-1, r.top+1, rs.bottom-1)));
    return l;
}


void traverse(Matrix A, int row, int col)  {
}

void example() {
    //suppose A is the matrix you are given and n is the size of the matrix
    Matrix A = new Matrix(n,n);
    List<Coordinates> l = traverseClockWise(new Region(1, n, 1, n));

    // to traverse it from top left counterclockwise
    for (int i=0; i<l.size(); i++) {
        traverse(A, l[i].col, l[i].row);
    }

    // to traverse it from the middle and clockwise
    for (int i=l.size()-1; i>=0; i--) {
        traverse(A, l[i].col, l[i].row);
    }

    // to traverse it from the middle and counterclockwise
    for (int i=l.size()-1; i>=0; i--) {
        traverse(A, l[i].row, l[i].col);
    }
}
0

More articles:


All Articles