1091. Shortest Path in Binary Matrix
Medium
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
andC_{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 valuegrid[0][0]
)C_k
is at location(N-1, N-1)
(ie. has valuegrid[N-1][N-1]
)- If
C_i
is located at(r, c)
, thengrid[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]
is0
or1
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