Shortest Path in Binary Matrix

In an N by N square grid, each cell is either empty (0) or blocked (1).

A clear path from top-left to bottom-right has length k if and only if it is composed of cells C_1, C_2, ..., C_k such that:

• Adjacent cells C_i and C_{i+1} are connected 8-directionally (ie., they are different and share an edge or corner)

• C_1 is at location (0, 0) (ie. has value grid[0][0])

• C_k is at location (N-1, N-1) (ie. has value grid[N-1][N-1])

• If C_i is located at (r, c), then grid[r][c] is empty (ie. grid[r][c] == 0).

Return the length of the shortest such clear path from top-left to bottom-right. If such a path does not exist, return -1.

Example 1:

Input: [[0,1],[1,0]]


Output: 2

Example 2:

Input: [[0,0,0],[1,1,0],[1,1,0]]


Output: 4

Note:

1. 1 <= grid.length == grid[0].length <= 100

2. grid[r][c] is 0 or 1

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid[0][0] == 1 || grid[grid.length - 1][grid[0].length - 1] == 1)
            return -1;
        int[][] dir = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }, { 1, 1 }, { 1, -1 }, { -1, 1 }, { -1, -1 } };
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] { 0, 0 });
        int steps = 1;
        while (q.size() != 0) {
            int size = q.size();
            while (size-- > 0) {
                int[] pos = q.poll();
                if (pos[0] == grid.length - 1 && pos[1] == grid[0].length - 1)
                    return steps;
                if (visited[pos[0]][pos[1]])
                    continue;
                visited[pos[0]][pos[1]] = true;
                for (int i = 0; i < 8; i++) {
                    int newX = pos[0] + dir[i][0], newY = pos[1] + dir[i][1];
                    if (newX >= 0 && newX < grid.length && newY >= 0 && newY < grid[0].length && grid[newX][newY] == 0)
                        q.add(new int[] { newX, newY });
                }
            }
            steps++;
        }
        return -1;
    }
}