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.
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