Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# zigzag traverse a matrix

Sanjeev Mehta
Greenhorn
Posts: 26
I want to traverse a matrix in zig-zag fashion.

Say my matrix is

a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44

I want my output to be

a11 a12 a21 a31 a22 a13 a14 a23 a32 a41 a42 a33 a24 a34 a43 a44.

I have tried doing it using nested if's and else's and it works but the code is messy. I want to know what a clean approach to achieve this should be.

Thanks

Rob Spoor
Sheriff
Posts: 20709
68
Let's look at the algorithm:
1) start at 1,1 (x == 1, y == 1)
2) move right once (x++)
3) move to the bottom left (x--, y++) until you've reached the left or bottom side
4) move to the bottom (y++)
5) move to the top right (x++, y--) until you've reached the right or top side
6) go to step 2 until you've reached the last cell

A simple loop would now do the trick. Keep in mind that Java arrays start at 0, not 1, so my values for x and y in step 1 are wrong.

Sanjeev Mehta
Greenhorn
Posts: 26
Thanks Rob. But wouldn't there be two loops involved? Because for the lower triangular matrix the traverse order would be :

1. move right once
2. move to the top right
3. move down once
4. move to the bottom left.

Sanjeev Mehta
Greenhorn
Posts: 26
This is how I implement this atm for an 8x8 matrix