/
Solution.java
50 lines (46 loc) · 1.74 KB
/
Solution.java
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package g1001_1100.s1091_shortest_path_in_binary_matrix;
// #Medium #Array #Breadth_First_Search #Matrix
// #Algorithm_II_Day_8_Breadth_First_Search_Depth_First_Search
// #Graph_Theory_I_Day_5_Matrix_Related_Problems
// #2022_02_23_Time_22_ms_(69.99%)_Space_59.9_MB_(35.14%)
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
private int[] directions = new int[] {0, 1, 1, 0, -1, 1, -1, -1, 0};
public int shortestPathBinaryMatrix(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
if (grid[0][0] == 1 || grid[m - 1][n - 1] == 1) {
return -1;
}
int minPath = 0;
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] {0, 0});
boolean[][] visited = new boolean[m][n];
visited[0][0] = true;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] curr = queue.poll();
if (curr[0] == m - 1 && curr[1] == n - 1) {
return minPath + 1;
}
for (int j = 0; j < directions.length - 1; j++) {
int newx = directions[j] + curr[0];
int newy = directions[j + 1] + curr[1];
if (newx >= 0
&& newx < n
&& newy >= 0
&& newy < n
&& !visited[newx][newy]
&& grid[newx][newy] == 0) {
queue.offer(new int[] {newx, newy});
visited[newx][newy] = true;
}
}
}
minPath++;
}
return -1;
}
}