Given a matrix with 0s and 1s where where 0 being empty cell and 1 being a blocked cell. Return the path in coordinates from the first cell to the last cell in matrix(if exists).
Answer should be ([0,0], [1,0], [1,1], [2,1], [2,2], [2,3], [3,3]).
This is my current implementation using BFS in c#:
int[][] matrix = new int[][]
{
new int[] { 0, 1, 0, 0 },
new int[] { 0, 0, 1, 0 },
new int[] { 1, 0, 0, 0 },
new int[] { 0, 1, 1, 0 }
};
public static List<IList<int>> FindPath(int[][] matrix)
{
var result = new List<IList<int>>();
if (matrix == null || matrix.Length == 0) return result;
int rows = matrix.Length, cols = matrix[0].Length;
bool[,] visited = new bool[rows, cols];
int[] dx = new int[] { 1, -1, 0, 0 }, dy = new int[] { 0, 0, -1, 1 };
var queue = new Queue<(int, int)>();
queue.Enqueue((0, 0));
while(queue.Count > 0)
{
var (r,c) = queue.Dequeue();
visited[r, c] = true;
if(r == rows-1 && c == cols - 1)
{
result.Add(new List<int> { r, c });
return result;
}
for(int i = 0; i < 4; i++)
{
var row = dx[i] + r;
var col = dy[i] + c;
if(row >= 0 && row < rows && col >= 0 && col < cols && !visited[row,col] && matrix[row][col] == 0)
{
queue.Enqueue((row, col));
result.Add(new List<int> { row, col });
}
}
}
return new List<IList<int>>();
}
I do not want to include just any cell with “0”. I only want the cells that I can move from. How can I fix this plz