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 in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

  • All the visited cells of the path are 0.
  • All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).

The length of a clear path is the number of visited cells of this path.

Examples

Example 1:

$$ \begin{matrix} \colorbox{lightgreen}0 & 1 \\ 1 & \colorbox{lightgreen}0 \end{matrix} $$

Input: grid = [[0,1],[1,0]]
Output:
 2

Example 2:

$$ \begin{matrix} \colorbox{lightgreen} 0 & \colorbox{lightgreen} 0 & 0 \\ 1 & 1 & \colorbox{lightgreen}0 \\ 1 & 1 & \colorbox{lightgreen}0 \end{matrix} $$

Input:
grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4

Example 3:

Input:
grid = [[1,0,0],[1,1,0],[1,1,0]]
Output: -1

Similar Problem

Find the Shortest Path between 2 cells in boolean maze

Solution

Method 1 - Using BFs

To solve the problem of finding the shortest clear path in a binary matrix, we will use Breadth-First Search (BFS) because BFS explores all nodes at the present depth level before moving on to nodes at the next depth level. This ensures we find the shortest path in an unweighted grid.

Here are the steps:

  1. Check Edge Cases: First, we need to ensure that the starting point (0,0) and the destination point (n-1,n-1) are not blocked (i.e., they should be 0). If either is blocked, return -1.
  2. BFS Initialization: Use a queue to perform BFS. Start from the top-left cell and explore all 8 possible directions (up, down, left, right, and the four diagonals).
  3. Mark Visited Cells: Use a matrix to keep track of visited cells to avoid revisiting them and getting stuck in cycles.
  4. Explore Neighbours: For each cell, add its valid neighbours to the queue if they are 0 and have not been visited yet.
  5. Return Path Length: When the BFS reaches the bottom-right cell, return the path length. If the queue is exhausted and the bottom-right cell is not reached, return -1.

Code

Java
class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        
        // Edge case: start or end is blocked
        if (grid[0][0] != 0 || grid[n-1][n-1] != 0) {
            return -1;
        }

        int[][] directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0});
        grid[0][0] = 1; // mark as visited by using the distance

        while (!q.isEmpty()) {
            int[] cell = q.poll();
            int r = cell[0], c = cell[1];
            int d = grid[r][c];

            if (r == n - 1 && c == n - 1) {
                return d;
            }

            for (int[] dir : directions) {
                int nr = r + dir[0], nc = c + dir[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0) {
                    q.add(new int[]{nr, nc});
                    grid[nr][nc] = d + 1;
                }
            }
        }

        return -1;
    }
}
Python
class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        n: int = len(grid)
        
        # Edge case: start or end is blocked
        if grid[0][0] != 0 or grid[n-1][n-1] != 0:
            return -1

        directions: List[tuple[int, int]] = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        q: deque = deque([(0, 0)])
        grid[0][0] = 1

        while q:
            r, c = q.popleft()
            d: int = grid[r][c]
            
            if r == n - 1 and c == n - 1:
                return d

            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                    q.append((nr, nc))
                    grid[nr][nc] = d + 1

        return -1

Complexity

  • ⏰ Time complexity: O(n^2) because in the worst case, we might need to explore all cells in the grid.
  • 🧺 Space complexity: O(n^2) due to the storage required for the queue and the visited matrix.