Diagonal Traversal of Matrix using DFS

I’ve encountered this problem in an Online Assessment(OA), the requirement was not exactly traversing diagonally, but I had to do something traversing diagonally.

Thinking about it during my OA hurt my brain, I had to think, after I put decent amount of thought into it, I was able to write a very messy code to do the job.

I wanted to give it another shot after the OA and ended up making it even messier but manageable, I wanted to use DFS as I was solving some questions related to Maze and paths in a maze.

Traversing Matrix diagonally

Above is the visual representation,
Now If we pick the first element 1 at (0,0) it has no valid neighbors diagonally
If we move onto element 2 at say i,j=(0,1) it as a valid neighbors at
(i+1, j-1) = (1,0)
For element 3 at i,j=(0,2), we have to move on until we find an invalid i,j by incrementing i (moving down) and decrementing j (moving left)
We would end up having (0,2)->(1,1) and (2,0)
We can add these to our stack until no valid neighbors and then print before popping them off.

With an objective to simplify it, I might’ve overdone it.

vector<vector<int>> matrix = {  
{1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,16}
};

This is the same matrix in the above png.

vector<vector<bool>> visited(matrix.size(), vector<bool>(matrix[0].size(), false));
//Just not to revisit the traversed vertices.

Core DFS Logic ahead

Output:

1
5       2
9       6       3
13      10      7       4
14      11      8
15      12
16