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.
Can anyone provide me with an easy-to-understand code with some explanation?
>Solution :
When you break down the logic into 2 steps, it becomes easy:
- 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.
- 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.
I will use a very basic Matrix class and name the variables r for row and c for column. As a life advice, I generally recommend you try to more meaningfully name your 1-letter loop variables than just the default i/j; it requires no extra-effort and can only make things clearer.
std::setw is used to keep the alignment of numbersj but it can be removed if it creates spaces you dislike.
#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 (ptrdiff_t r = m.rows - 1; r >= 0; --r) {
for (int i = 0; i + r < m.rows && i + r < m.columns; ++i)
std::cout << std::setw(3) << m[r + i][i];
std::cout << '\n';
}
for (ptrdiff_t c = 1; c < m.columns; ++c) {
for (int 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;
}