15,662,754 members

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; }

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.

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