DSA problem
Shortest Path in Binary Matrix
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 every visited cell is 0 and adjacent cells are 8-directionally connected. The length of a clear path is the number of visited cells.
The problem is an unweighted shortest-path search on an implicit grid graph with 8-directional adjacency. Each cell has up to 8 neighbours (horizontal, vertical, and diagonal), and the cost to move between any two adjacent open cells is one step.
Since every edge has the same unit weight, BFS finds the optimum. Push the start cell (0, 0) with distance 1 (the start counts toward the path length per the problem statement). Pop the next cell, and for each of the 8 neighbouring positions that are inside the grid and still 0, mark the neighbour visited and enqueue it with distance increased by 1. The first time we dequeue (n - 1, n - 1), the distance is the answer.
This runs in O(n^2) time because each cell enters the queue at most once, and O(n^2) space for the queue plus the visited matrix (or, in many implementations, the grid is marked in place to save the visited matrix). Special edge cases: if the start or end cell is 1 the answer is immediately -1; if n == 1 the answer is 1.
Examples
grid = [[0,1],[1,0]]2grid = [[0,0,0],[1,1,0],[1,1,0]]4grid = [[1,0,0],[1,1,0],[1,1,0]]-1Constraints
- n == grid.length
- n == grid[i].length
- 1 <= n <= 100
- grid[i][j] is 0 or 1.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.