Friday 29 April 2011

Traverse an array diagonally

 

Question

   How would you traverse an array diagonally and display its contents ?

Say you have something like this,

1  2  3
4  5  6
7  8  9
In the above array, if you traverse from top left corner, then the list of number will be,
[1], [2,4], [3,5,7], [6,8], [9]
How would you get the above set?
Solution
Reference: http://stackoverflow.com/questions/1779199/traverse-matrix-in-diagonal-strips
     0     1     2
0   1     2     3
1    4    5     6
2    7    8     9
The list of indices for the required traversals are,
{[0,0]}  {[0,1][1,0]}  {[0,2][1,1][2,0]}  {[1,2][2,1]} {[2,2]}
If you can get the pattern, then you can do this easily. Total 5 slices will come which is array size N * 2-1. i.e, for 3x3 = 6-1 = 5.
you should have a incrementing counter at row/column when moving to the middle slice. After that you need a decrementing counter at row/column.
Code
void main()
{
    int x[3][3] = {1, 2, 3,
                   4, 5, 6,
                   7, 8, 9};
    int N=3;
    for (int slice = 0; slice < N*2-1; ++slice) {
        int z = slice < N ? 0 : slice - N + 1;
        for (int j = z; j <= slice - z; ++j) {
            int c1=j;
            int c2=(N-1)-(slice-j);
            printf("%d ", x[c1][c2]);
        }
        printf("\n");
    }
    
    printf("\n");
    for (int slice = 0; slice < N*2-1; ++slice) {
        int z = slice < N ? 0 : slice - N + 1;
        for (int j = z; j <= slice - z; ++j) {
            int c1=j;
            int c2=slice-j;
            printf("%d ", x[c1][c2]);
        }
        printf("\n");
    }
}
  • here slice maintains the incrementing/decrementing index required. slice-N+1 will take care of that value
  • slice-j allows as move in both row and column.
  • When you need to move from top right, just subtract N-1 from slice-j so that you also travel from top right.
Output
Top right to bottom left

3
2 6
1 5 9
4 8
7

Top left to bottom right

1
2 4
3 5 7
6 8
9

 
 

No comments:

Post a Comment