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

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