Click here to Skip to main content
15,901,666 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
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

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900