Back to DSA

Shortest Path in Binary Matrix

medium
Acceptance: 44%
GraphsBFS

In an n-by-n binary grid (0 = passable, 1 = blocked), find the length of the shortest path from the top-left to the bottom-right cell. Movement is allowed in all eight directions (including diagonals). The path length counts the number of cells visited. Return -1 if no such path exists.

Examples

Example 1:
Input:grid = [[0,0,1],[0,0,0],[1,0,0]]
Output:3
Explanation: Path (0,0) -> (1,1) -> (2,2) visits 3 cells.
Example 2:
Input:grid = [[0,1],[1,0]]
Output:-1
Explanation: No clear path exists because the cells adjacent to start and end are blocked.

Hints

Related Problems

Clone GraphmediumPacific Atlantic Water FlowmediumRotting OrangesmediumWalls and GatesmediumOpen the Lockhard
00:00
import java.util.*;

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if (grid[0][0] != 0 || grid[n-1][n-1] != 0) return -1;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, 1});
        grid[0][0] = 1;
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            if (cell[0] == n-1 && cell[1] == n-1) return cell[2];
            for (int[] d : dirs) {
                int nr = cell[0] + d[0], nc = cell[1] + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0) {
                    grid[nr][nc] = 1;
                    queue.offer(new int[]{nr, nc, cell[2] + 1});
                }
            }
        }
        return -1;
    }
}
Time complexityO(n^2)
Space complexityO(n^2)