Grokking 197

class Solution {

  int[][] DIRS = new int[][] { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1} };

  public int shortestPathBinaryMatrix(int[][] grid) {
    int n = grid.length;

    if (grid == null || grid[0][0] != 0 || grid[n - 1][n - 1] != 0) {
      return -1;
    }

    Queue<int[]> queue = new LinkedList();
    queue.offer(new int[] {0 , 0});

    grid[0][0] = 1;

    while (!queue.isEmpty()) {
      int[] cell = queue.poll();
      int r = cell[0];
      int c = cell[1];

      int distance = grid[r][c];

      // if met destination, return distance
      if (r == n - 1 && c == n - 1) {
        return distance;
      }

      // explore all neighbor rows and update new distance
      for (int i = 0; i < 8; i++) {
        int[] dir = DIRS[i];

        int rr = r + dir[0];
        int cc = c + dir[1];

        if (0 <= rr && rr < n && 0 <= cc && cc < n && grid[rr][cc] == 0) {
          grid[rr][cc] = distance + 1;

          queue.offer(new int[] {rr, cc});
        }
      }
    }

    return -1;
  }
}