Shortest Distance
in a Binary Maze using BFS

Problem Statement

Given an n × m binary matrix grid where each cell can be either 0 or 1, find the shortest path between a source cell and a destination cell. You can only move to a cell with value 1 and you may move only in four directions: up, down, left, and right.

If the path between the source and destination is not possible, return -1.

Note: The source and destination cells must also be 1 to begin with, or the path is impossible.

Algorithm Steps

1. Check if the source or destination cell is 0. If yes, return -1.
2. Initialize a 2D array dist with Infinity. Set the distance for the source cell to 0.
3. Create a queue and add the source cell to it.
4. While the queue is not empty:
1. Pop the front cell (x, y) and its distance d.
2. For each of the four directions (up, down, left, right):
1. Compute new cell coordinates (nx, ny).
2. If (nx, ny) is within bounds, has value 1, and not yet visited or has a longer distance:
• Update dist[nx][ny] = d+1.
• Enqueue (nx, ny, d+1).
5. If the destination is reached, return dist[destX][destY].
6. If the queue is empty and destination was never reached, return -1.

Code

function shortestPathBinaryMaze(grid, source, destination) {
  const [n, m] = [grid.length, grid[0].length];
  const [srcX, srcY] = source;
  const [destX, destY] = destination;

  if (grid[srcX][srcY] === 0 || grid[destX][destY] === 0) return -1;

  const directions = [[0,1],[1,0],[0,-1],[-1,0]];
  const dist = Array.from({ length: n }, () => Array(m).fill(Infinity));
  dist[srcX][srcY] = 0;

  const queue = [[srcX, srcY, 0]];

  while (queue.length > 0) {
    const [x, y, d] = queue.shift();

    for (const [dx, dy] of directions) {
      const [nx, ny] = [x + dx, y + dy];

      if (nx >= 0 && ny >= 0 && nx < n && ny < m && grid[nx][ny] === 1 && d + 1 < dist[nx][ny]) {
        dist[nx][ny] = d + 1;
        queue.push([nx, ny, d + 1]);
      }
    }
  }

  return dist[destX][destY] === Infinity ? -1 : dist[destX][destY];
}

const grid = [[1,1,1],[0,1,0],[1,1,1]];
console.log("Shortest Distance:", shortestPathBinaryMaze(grid, [0,0], [2,2])); // Output: 4