This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#1091) before relying on it.

Shortest Path in Binary Matrix

An interactive visualization of BFS wavefront expansion on an N×N binary grid. Watch the algorithm explore all 8 directions level by level and find the shortest clear path from top-left to bottom-right.

BFS LeetCode 1091 ↗ Medium

The Problem

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path is a path from the top-left cell (0, 0) to the bottom-right cell (n-1, n-1) such that:

• All visited cells are 0 (open).
• All adjacent cells in the path are 8-directionally connected (they differ in at most one row and one column).

The length of a path is the number of visited cells in the path.

Interactive Visualization

Grid (rows on separate lines, or ; separated)

Preset

Speed:

Grid

Open (0)

Blocked (1)

Processing

Current wave

Visited

Shortest path

BFS Queue (front → back)

Empty — will fill as BFS runs

Code

fun shortestPathBinaryMatrix(grid: Array<IntArray>): Int {    val n = grid.size    if (grid[0][0] != 0 || grid[n-1][n-1] != 0)        return -1    val queue: ArrayDeque<Triple<Int,Int,Int>> = ArrayDeque()    queue.add(Triple(0, 0, 1))    grid[0][0] = 1  // mark visited    val dirs = arrayOf(intArrayOf(-1,-1),intArrayOf(-1,0),intArrayOf(-1,1),            intArrayOf(0,-1),        intArrayOf(0,1),            intArrayOf(1,-1), intArrayOf(1,0), intArrayOf(1,1))    while (queue.isNotEmpty()) {        val (r, c, dist) = queue.removeFirst()        if (r == n-1 && c == n-1)            return dist        for (d in dirs) {            val nr = r + d[0]; val nc = c + d[1]            if (nr in 0 until n && nc in 0 until n && grid[nr][nc] == 0) {                grid[nr][nc] = 1                queue.add(Triple(nr, nc, dist+1))            }        }    }    return -1}

def shortestPathBinaryMatrix(grid):    n = len(grid)    if grid[0][0] or grid[n-1][n-1]:        return -1    queue = deque([(0, 0, 1)])    grid[0][0] = 1  # mark visited    dirs = [(-1,-1),(-1,0),(-1,1),            (0,-1),        (0,1),            (1,-1), (1,0), (1,1)]    while queue:        r, c, dist = queue.popleft()        if r == n-1 and c == n-1:            return dist        for dr, dc in dirs:            nr, nc = r + dr, c + dc            if 0<=nr<n and 0<=nc<n and not grid[nr][nc]:                grid[nr][nc] = 1                queue.append((nr, nc, dist+1))    return -1

Current Step

Press Step or Play to begin.

How It Works

Key Insight

BFS explores cells level by level (wavefront expansion). Since every move costs 1 step, the first time BFS reaches the destination (n-1, n-1), the distance is guaranteed to be the shortest path. This is the fundamental property of BFS on unweighted graphs.

The Algorithm

Check start/end: if either grid[0][0] or grid[n-1][n-1] is blocked (1), return -1 immediately.
Initialize: enqueue the start cell (0, 0) with distance 1, and mark it visited.
BFS loop: dequeue a cell (r, c, dist).
— If it is the target (n-1, n-1): return dist.
— Otherwise, explore all 8 neighbors. For each unvisited open neighbor, mark it visited and enqueue with dist + 1.
If the queue empties without reaching the target, return -1 — no path exists.

Why 8 Directions?

Unlike typical grid problems that use 4-directional movement (up/down/left/right), this problem allows diagonal movement. This means from any cell, we can move to any of its 8 neighbors — including diagonals. This is why the directions array includes (-1,-1), (-1,1), (1,-1), (1,1) in addition to the 4 cardinal directions.

Complexity

Time O(n²)

Space O(n²)

Each cell is visited at most once, and for each cell we check 8 neighbors — so the total work is O(n²). The queue and visited markers both use O(n²) space.