Zig zag (a challenge)

This time I’m going to propose a challenge. I’m thinking mainly of young programmers who would like to take part in events like the ONI (or the IOI). If this has any success, I’ll propose another challenge.

The challenge is the following:

Produce a zig-zag array.

A zig-zag array is a square array of the first N2 integers, where the numbers run from lowest to highest, laid out in a zig-zag along the anti-diagonals of the matrix (see the figure).

For example, if N is 5, the program must produce this array:

0 1 5 6 14 2 4 7 13 15 3 8 12 16 21 9 11 17 20 22 10 18 19 23 24

• Although this may look like a brain teaser, and a somewhat useless one, the truth is that this kind of array is used in the JPEG image compression algorithm.