Skip to content

1091. 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 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.

Example 1:

img

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

Example 2:

img

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

Constraints:

  • n == grid.length
  • n == grid[i].length
  • 1 <= n <= 100
  • grid[i][j] is 0 or 1

Solution:

class Solution {
    int[][] directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
    // public int result;
    public int shortestPathBinaryMatrix(int[][] grid) {

        int n = grid.length;
        if (n == 1 && grid[0][0] == 0){
            return 1;
        }

        // bfs 
        // queue

        int x = 0;
        int y = 0;
        int index = 0;
        int[][] visited = new int[n][n];
        return bfs(x, y, grid, n, index, visited);
    }

    private int bfs(int x, int y, int[][] grid, int n, int index, int[][] visited){
        Deque<int[]> queue = new ArrayDeque<int[]>();
        if (grid[x][y] != 0){
            return -1;
        }
        queue.offerLast(new int[]{x,y});
        visited[0][0] = 1;


        while(!queue.isEmpty()){
            int size = queue.size();
            index++;
            for (int i = 0; i < size; i++){
                int[] cur = queue.pollFirst();
                int curX = cur[0];
                int curY = cur[1];
                if (curX == n - 1 && curY == n -1){
                    return index;
                }

                for (int[] dir : directions){
                    int nextX = dir[0] + curX;
                    int nextY = dir[1] + curY;
                    if(nextX >= 0 && nextY >= 0 && nextX < n && nextY < n && visited[nextX][nextY] == 0 && grid[nextX][nextY] == 0){
                        queue.offerLast(new int[]{nextX, nextY});
                        visited[nextX][nextY] = 1;
                    }
                }

            }



        }

        return -1;




    }
}

// TC: O(n^2)
// SC: O(n^2)