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.

Examples❯

Grid	Source	Destination	Shortest Distance	Description
[[1,1,1],[0,1,0],[1,1,1]]	(0,0)	(2,2)	4	Moves: (0,0) → (0,1) → (1,1) → (2,1) → (2,2)
[[1,0,1],[1,1,0],[0,1,1]]	(0,0)	(2,2)	4	Valid path exists avoiding 0s
[[1,0,0],[0,0,0],[0,0,1]]	(0,0)	(2,2)	-1	No valid path exists
[[1]]	(0,0)	(0,0)	0	Start and end are the same
[[0]]	(0,0)	(0,0)	-1	Cell is 0; not walkable

Solution❯

To find the shortest path in a binary maze, we use the Breadth-First Search (BFS) algorithm, as it naturally finds the shortest distance in unweighted graphs. Here, the maze cells represent graph nodes and adjacent walkable cells (value 1) represent edges.

We use a queue to perform BFS traversal, and track the distance from the source using a 2D dist array initialized with Infinity. A cell is processed only if:

It is within bounds.
It contains the value 1.
It hasn't already been visited with a shorter path.

We update distances while moving in four directions: up, down, left, and right. When we reach the destination, we return the current distance. If BFS ends without visiting the destination, the return value is -1.

Algorithm Steps❯

Check if the source or destination cell is 0. If yes, return -1.
Initialize a 2D array dist with Infinity. Set the distance for the source cell to 0.
Create a queue and add the source cell to it.
While the queue is not empty:

Pop the front cell (x, y) and its distance d.
For each of the four directions (up, down, left, right):

Compute new cell coordinates (nx, ny).
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).

If the destination is reached, return dist[destX][destY].
If the queue is empty and destination was never reached, return -1.

Code

JavaScript

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

⬅ Previous TopicDijkstra’s Algorithm Using Priority Queue

Next Topic ⮕Path With Minimum Effort in Grid using Graphs