15,879,326 members
See more:
So I've implemented a BFS search algorithm to find the shortest path from the first index in the binary matrix (top left) to the last index (bottom right).

I would now like to trace back the path that I found, but I have no idea how to keep track of the parent node and when to actually add it to a data structure.

```int[][] dirs = new[]
{
new[] { 0, 1 }, //Bottom
new[] { 1, 1 }, //Bottom right
new[] { 1, 0 }, //Right
new[] { 1, -1 }, //Top right
new[] { 0, -1 }, //Top
new[] { -1, -1 }, //Top left
new[] { -1, 0 }, //Left
new[] { -1, 1 } //Bottom left
};

public int BinaryMatrix(int[][] grid)
{
/* Length of the rows */
var rowLength = grid.Length;

/* The length of each col */
var colLength = grid[0].Length;

/* Can't find a path */
if (grid[0][0] == 1 || grid[rowLength - 1][colLength - 1] == 1)
return -1;

var Queue = new Queue<int[]>(); /* Coordinates */

/* Make a copy of the grid on order to update and perform checks without manipulating the original one. */
int[][] visited = new int[rowLength][];
for (int i = 0; i < visited.Length; i++)
visited[i] = new int[colLength];

Queue.Enqueue(new[] { 0, 0 });
visited[0][0] = 2;
int steps = 1;

while (Queue.Count != 0)
{
int levelSize = Queue.Count;

for (int r = 0; r < levelSize; r++)
{
int[] coord = Queue.Dequeue();
var cy = coord[0]; /* Y */
var cx = coord[1]; /* X */

/* If what we just popped has the same coordinates as the destination */
if (cy == rowLength - 1 && cx == colLength - 1)
{
/* Traceback */
return steps;
}

for (int i = 0; i < dirs.Length; i++)
{
int neighborY = dirs[i][0] + cy;
int neighborX = dirs[i][1] + cx;

/* Bounds check */
if (neighborX >= 0 && neighborX < colLength && neighborY >= 0 && neighborY < rowLength)
{
/* Visited check */
if (visited[neighborY][neighborX] == 0 &&
grid[neighborY][neighborX] == 0)
{
Queue.Enqueue(new[] { neighborY, neighborX });
visited[neighborY][neighborX] = 2;
}
}
}
}

/* Increment once we're done traversing through a level */
steps++;
}
return -1;
}```

What I have tried:

I've tried keeping track of the parent node but I kept getting every other node as well. So I'm not sure how to.
Posted