Diagonal search algorithm

Question

I am looking to implement a diagonal searching algorithm that is continuous. This means it is one long unbroken line that is going from the top of a MxN grid and then continuously iterating until the end without jumping to calculate each diagonal.

I have been trying to figure out this algorithm but I just don't see it. I will upload images of my work below. I am trying to write this algorithm in Java or C and then I will be converting it to MIPS. I am just having trouble trying to find the actual algorithm.

Answer 1

Here is an example in C to calculate the x and y coordinates iteratively for a zigzag walk of the 2D array:

#include <stdio.h>

#define M 10
#define N 8

int main(void) {
    int mat[M][N];

    for (int x = 0, y = 0, dx = 1, n = 0; n < M * N; n++) {
        mat[y][x] = n;
        x += dx;
        y -= dx;
        if (x == N) {
            /* exit to the right: go S then SW */
            x -= 1;
            y += 2;
            dx = -1;
        } else
        if (y < 0) {
            /* exit to the top: go E then SW */
            y += 1;
            dx = -1;
        } else
        if (y == M) {
            /* exit to the bottom: go E then NE */
            x += 2;
            y -= 1;
            dx = 1;
        } else
        if (x < 0) {
            /* exit to the left: go S then NE */
            x += 1;
            dx = 1;
        }
    }
    for (int y = 0; y < M; y++) {
        for (int x = 0; x < N; x++) {
            printf(" %3d", mat[y][x]);
        }
        printf("\n");
    }
    return 0;
}

Output:

   0   1   5   6  14  15  27  28
   2   4   7  13  16  26  29  43
   3   8  12  17  25  30  42  44
   9  11  18  24  31  41  45  58
  10  19  23  32  40  46  57  59
  20  22  33  39  47  56  60  69
  21  34  38  48  55  61  68  70
  35  37  49  54  62  67  71  76
  36  50  53  63  66  72  75  77
  51  52  64  65  73  74  78  79

Here is an alternative without an extra variable, using the parity of x + y:

#include <stdio.h>

#define M 10
#define N 8

int main(void) {
    int mat[M][N];

    for (int x = 0, y = 0, n = 0; n < M * N; n++) {
        mat[y][x] = n;
        if ((x + y) & 1) {
            if (y == M - 1) {
                /* exit to the bottom: go E */
                x += 1;
            } else
            if (x == 0) {
                /* exit to the left: go S */
                y += 1;
            } else {
                /* follow the NE diagonal */
                x -= 1;
                y += 1;
            }
        } else {
            if (x == N - 1) {
                /* exit to the right: go S */
                y += 1;
            } else
            if (y == 0) {
                /* exit to the top: go E */
                x += 1;
            } else {
                /* follow the NE diagonal */
                x += 1;
                y -= 1;
            }
        }
    }
    for (int y = 0; y < M; y++) {
        for (int x = 0; x < N; x++) {
            printf(" %3d", mat[y][x]);
        }
        printf("\n");
    }
    return 0;
}

Answer 2

Continuing on @user85421's suggestion, in the map below the colors tell the direction to the next cell.

The checkerboard pattern (alternating yellow and green) is easily decided by testing the parity of x+y. Replacing yellow by red or green by blue on edges is straightforward, though there is a special case bottom left.

Answer 3

It seems the algorithm can be described as:

1. Move 1 step right. If not possible move 1 step down. If not possible goto 6.

2. Move diagonal down-left as long as possible. If not possible at all goto 6.

3. Move 1 step down. If not possible move 1 step right. If not possible goto 6.

4. Move diagonal right-up as long as possible. If not possible at all goto 6.

5. Goto step 1.

6. Done, i.e. all elements have been visited

Answer 4

Since x+y is constant along each diagonal, I would do it like this:

// x+y is constant along each diagonal
for (int sumxy = 0; sumxy < M+N-1; ++sumxy) {
  // determine the range of y-x
  // 2x = sumxy-diffyx => 0 <= sumxy-diffyx <= 2M-2 => sumxy-2M+2 <= diffyx <= sumxy
  // 2y = sumxy+diffyx => 0 <= sumxy+diffyx <= 2N-2 => -sumxy <= diffyx <= 2N-2-sumxy
  int mindiff = max(sumxy-2*M+2, -sumxy);
  int maxdiff = min(sumxy, 2*N-2-sumxy);
  for (int d=0; d <= maxdiff-mindiff; d+=2) {
    // odd sum => increasing diff, even sum => decreasing
    int diffyx = (sumxy & 1) ? mindiff + d : maxdiff - d;
    int x = (sumxy-diffyx) >> 1;
    int y = (sumxy+diffyx) >> 1;
    // process (x,y)
  }
}