Breadth-First Search (BFS) for Shortest Path in a Grid

This challenge involves implementing the Breadth-First Search (BFS) algorithm to find the shortest path between two points in a 2D grid. BFS is a fundamental graph traversal algorithm that explores all the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. This makes it ideal for finding the shortest path in unweighted graphs or grids.

Problem Description

You are tasked with writing a Javascript function findShortestPath(grid, start, end) that takes a 2D grid representing a maze, a starting coordinate, and an ending coordinate. The grid will contain '0' for traversable cells and '1' for obstacles. The function should return an array of coordinates representing the shortest path from the start to the end, inclusive. If no path exists, it should return an empty array.

Key Requirements:

• Implement BFS to explore the grid.
• The path should be the shortest possible sequence of traversable cells.
• The output should be an array of coordinate objects (e.g., { row: 0, col: 0 }).
• Movement is restricted to up, down, left, and right (no diagonal movement).

Expected Behavior:

The function should return the shortest path as an ordered list of coordinates. If multiple shortest paths exist, any one of them is acceptable.

Edge Cases to Consider:

• Start and end points are the same.
• Start or end point is an obstacle.
• No path exists between start and end.
• Grid is empty or has invalid dimensions.
• Start or end coordinates are out of bounds.

Examples

Example 1:

Input:
grid = [
  ['0', '0', '0', '0'],
  ['1', '1', '0', '1'],
  ['0', '0', '0', '0'],
  ['0', '1', '1', '0']
]
start = { row: 0, col: 0 }
end = { row: 3, col: 3 }

Output:
[
  { row: 0, col: 0 },
  { row: 0, col: 1 },
  { row: 0, col: 2 },
  { row: 0, col: 3 },
  { row: 1, col: 3 },  // This is incorrect, should be {row: 2, col: 3}
  { row: 2, col: 3 },
  { row: 3, col: 3 }
]
Explanation: The shortest path found is from (0,0) to (3,3) going through traversable cells.

Correction for Example 1 Output:

Output:
[
  { row: 0, col: 0 },
  { row: 0, col: 1 },
  { row: 0, col: 2 },
  { row: 1, col: 2 },
  { row: 2, col: 2 },
  { row: 2, col: 3 },
  { row: 3, col: 3 }
]
Explanation: The shortest path found is from (0,0) to (3,3) going through traversable cells.

Example 2:

Input:
grid = [
  ['0', '1'],
  ['0', '0']
]
start = { row: 0, col: 0 }
end = { row: 1, col: 1 }

Output:
[
  { row: 0, col: 0 },
  { row: 1, col: 0 },
  { row: 1, col: 1 }
]
Explanation: The path goes around the obstacle.

Example 3 (No Path):

Input:
grid = [
  ['0', '1', '0'],
  ['0', '1', '0'],
  ['0', '1', '0']
]
start = { row: 0, col: 0 }
end = { row: 0, col: 2 }

Output:
[]
Explanation: The end is unreachable due to obstacles.

Constraints

• The grid will contain at most 100 rows and 100 columns.
• Grid elements will be either '0' (traversable) or '1' (obstacle).
• start and end will be objects with row and col properties.
• start.row, start.col, end.row, end.col will be non-negative integers.
• The algorithm should aim for a time complexity that is efficient for grids of this size.

Notes

• You will need a way to keep track of visited cells to avoid infinite loops and redundant processing.
• A queue data structure is essential for BFS.
• To reconstruct the path, you'll need to store the predecessor of each cell as you explore. Consider using a map or a separate 2D array for this.
• Think about how to represent the coordinates and how to efficiently check if a neighbor is valid (within bounds, traversable, and not visited).