Shortest Path in Binary Matrix

LeetCode Q 1091 - 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 <= grid.length == grid[0].length <= 100
• grid[r][c] is 0 or 1

Solution

Code:

public int shortestPathBinaryMatrix(int[][] grid) {
	
  int R = grid.length, C = grid[0].length;

  if (grid[0][0] == 1 || grid[R - 1][C - 1] == 1) return -1;

  int[] dirs = new int[] {1, 0, -1, 0, 1, 1, -1, -1, 1};
  boolean[][] visited = new boolean[R][C];

  Queue<int[]> que = new LinkedList<>(); // x, y-coordinate, dist
  que.offer(new int[]{0, 0, 1});
  visited[0][0] = true;

  while (!que.isEmpty()) {
    int[] curr = que.poll();
    int r = curr[0], c = curr[1];
    if (r == R - 1 && c == C - 1) return curr[2];

    for (int i = 0; i < 8; i++) {
    	int nr = r + dirs[i], nc = c + dirs[i + 1];

    	if (nr >= 0 && nr < R && nc >= 0 && nc < C && !visited[nr][nc] && grid[nr][nc] == 0) {
    		que.offer(new int[]{nr, nc, curr[2] + 1});
    		visited[nr][nc] = true;
    	}
    }
  }

  return -1;
}