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().
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, then:
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 the change of direction taking place at the top left corner of the matrix.
Matrix
class and name the variables r
for row and c
for column.i
/j
/k
/...; it requires no extra-effort and can only make things clearer.size_t
(unsigned) which usually is std::vector<int>::size_type
, just less verbose. As a result, the first outer loop cannot be left to handle the top-left cell of the matrix, or if you prefer, I cannot write its condition r >= 0
as it would result in a infinite loop.std::setw
is used to keep the alignment of numbers 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 (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;
}