-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathShortestPathBinaryMatrix.java
48 lines (39 loc) · 1.87 KB
/
ShortestPathBinaryMatrix.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
import java.util.*;
public class ShortestPathBinaryMatrix {
public static void main(String[] args) {
int[][] grid = { { 0, 0, 0 }, { 1, 1, 1 }, { 1, 1, 0 } };
System.out.println(shortestPathBinaryMatrix(grid));
}
public static int shortestPathBinaryMatrix(int[][] grid) {
int n = grid.length;
if (grid[0][0] == 1 || grid[n-1][n-1] == 1) {
return -1;
}
int[][] directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{0, 0});
grid[0][0] = 1;
int pathLength = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] curr = queue.poll();
int row = curr[0];
int col = curr[1];
if (row == n-1 && col == n-1) {
return pathLength;
}
for (int[] dir : directions) {
int newRow = row + dir[0];
int newCol = col + dir[1];
if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n && grid[newRow][newCol] == 0) {
queue.offer(new int[]{newRow, newCol});
grid[newRow][newCol] = 1;
}
}
}
pathLength++;
}
return -1; // No valid path found
}
}