c++algorithmdata-structures

how to traverse an NxN grid diagonally


I want to traverse an NxN grid diagonally in C++ but I am unable to find out the proper relationship or approach to do so,

For example, Grid is:

 1  2  3
-2  1 -1
 0  0 -1

Output should be:

0
-2 0
1 1 -1
2 -1
3

Which, after adding extra-spaces, looks a bit like the original grid:

    0
 -2   0
1   1  -1
  2  -1
    3

I did find a code for this on internet

for(int i=1-n; i<n; i++) {
    for(int j=max(0, -i); max(j, j+i)<n; j++) {
        cout << a[j][j+i] << " ";
    }
        cout<<endl;
}

but I am unable to understand this code or how does it work, I have even tried dry running it on paper.

I am having difficulty with doing it in one loop with max() function. Like, how does it take care of all the diagonals?

Is there any other version of this which involves multiple loops but avoids using functions like max() and min().


Solution

  • When you break down the logic into 2 steps, it becomes easy:

    1. Determine the starting cell of each diagonal. The first diagonal starts at the bottom left of your matrix and each successive diagonal starts 1 cell above the previous one. When you reach the first line, the following diagonals start 1 cell to the right of the previous one.
    2. Move diagonally until you reach the bottom or the right of the matrix.

    A simple nested loop can do the trick, or rather 2 consecutive nested loop to account for what happens when reaching the main diagonal of the matrix.

    #include <iomanip>
    #include <iostream>
    #include <vector>
    
    class Matrix
    {
    public:
        Matrix(size_t rowCount, size_t colCount) : rows(rowCount), columns(colCount), data(rowCount * colCount) {}
        int* operator[](size_t r) {
            return (&data[r * columns]);
        }
        size_t rows, columns;
        std::vector<int>data;
    };
    int main(int, char**)
    {
        Matrix m(3, 3);
        m.data = { 1, 2, 3, -2, 1, -1, 0, 0, -1 };
        for (size_t r = m.rows - 1; r > 0; --r) {
            for (size_t i = 0; i + r < m.rows && i + r < m.columns; ++i)
                std::cout << std::setw(3) << m[r + i][i];
            std::cout << '\n';
        }
        for (size_t c = 0; c < m.columns; ++c) {
            for (size_t i = 0; i + c < m.rows && i + c < m.columns; ++i)
                std::cout << std::setw(3) << m[i][c + i];
            std::cout << '\n';
        }
        return 0;
    }