1
class Solution {
2
  public int shortestPathBinaryMatrix(int[][] grid) {
3
    int m = grid.length, n = grid[0].length;
4

5
    boolean[][] visited = new boolean[m][n];
6

7
    int[] up = {0, 0, 1, -1, 1, 1, -1, -1};
8
    int[] down = {-1, 1, 0, 0, -1, 1, -1, 1};
9

10
    /*
11
    if top-left is 1 or bottom-right is 1
12
    we will return -1
13
    */
14
    if (grid[0][0] == 1 || grid[m - 1][n - 1] == 1) return -1;
15

16
    ArrayDeque<int[]> q = new ArrayDeque<>();
17
    /*
18
    we will add top-left to the deque
19
    ans steps as 1
20
    */
21
    q.add(new int[] {0, 0, 1});
22

23
    while (q.size() > 0) {
24
      int[] tmp = q.removeFirst();
25
      int x = tmp[0];
26
      int y = tmp[1];
27
      int steps = tmp[2];
28
      visited[x][y] = true;
29

30
      if (x == m - 1 && y == n - 1) return steps;
31

32
      for (int i = 0; i < 8; i++) {
33
        int x_new = x + up[i];
34
        int y_new = y + down[i];
35
        /*
36
        we will traverse level wise using bfs
37
        and those which can be directly reach via
38
        current level will be considered as the same
39
        level and we will return the level of
40
        bottom-right as result
41
        */
42
        if (x_new >= 0 && x_new < m && y_new >= 0 && y_new < n) {
43
          if (visited[x_new][y_new] == false && grid[x_new][y_new] == 0) {
44
            q.add(new int[] {x_new, y_new, steps + 1});
45
            visited[x_new][y_new] = true;
46
          }
47
        }
48
      }
49
    }
50

51
    return -1;
52
  }
53
}