Tuesday, November 3, 2020

LeetCode [1091] Shortest Path in Binary Matrix

1091. Shortest Path in Binary Matrix
Medium

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

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int[][] dirs = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 1 }, { 1, -1 }, { -1, 1 },
                { -1, -1 } };
        int m = grid.length, n = grid[0].length;

        if (grid[0][0] != 0)
            return -1;
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[] { 0, 0 });
        grid[0][0] = 1;
        int steps = 1;
        while (!que.isEmpty()) {
            int sz = que.size();
            for (int i = 0; i < sz; ++i) {
                int[] top = que.poll();
                int x = top[0], y = top[1];
                if (x == m - 1 && y == n - 1)
                    return steps;
                for (int[] d : dirs) {
                    int x1 = x + d[0], y1 = y + d[1];
                    if (x1 >= 0 && x1 < m && y1 >= 0 && y1 < n && grid[x1][y1] == 0) {
                        que.add(new int[] { x1, y1 });
                        grid[x1][y1] = 1;
                    }
                }
            }
            steps++;
        }

        return -1;
    }
}

No comments:

Post a Comment