Shortest Path in Binary Matrix

1091.Shortest Path in Binary Matrix

BFS

Matrix

Graph

Problem Statement:

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 to the bottom-right cell such that all visited cells are 0 and we can move in 8 directions.

Example:

Input:

grid = [[0,1],[1,0]]

→

Output:

2

Java Solution:

public int shortestPathBinaryMatrix(int[][] grid) {
    int dir[][] = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, -1}, {-1, 1}, {-1, -1}, {1, 1}};
    int m = grid.length;
    int n = grid[0].length;
    if (grid[0][0] == 1 || grid[m - 1][n - 1] == 1) return -1;
            
    boolean[][] visited = new boolean[m][n];
    visited[0][0] = true;
    Queue<int[]> queue = new LinkedList<>();
    queue.add(new int[]{0, 0});
    int ans = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
                
        // Use queue size method for distance
        for (int i = 0; i < size; i++) {
            int[] curr = queue.remove();
                    
            if (curr[0] == m - 1 && curr[1] == n - 1) return ans + 1;
                    
            for (int k = 0; k < 8; k++) {
                int nextX = dir[k][0] + curr[0];
                int nextY = dir[k][1] + curr[1];
                if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && 
                    !visited[nextX][nextY] && grid[nextX][nextY] == 0) {
                    queue.add(new int[]{nextX, nextY});
                    visited[nextX][nextY] = true;
                }
            }
        }
        ans++;
    }
    return -1;
}

Complexity:

Time: O(N×N) | Space: O(N×N)