8000 Add `Tree Breadth First Search/1293_Shortest_Path_in_a_Grid_with_Obst… · seanprashad/leetcode-patterns@e0cace7 · GitHub
[go: up one dir, main page]

Skip to content

Commit e0cace7

Browse files
committed
Add Tree Breadth First Search/1293_Shortest_Path_in_a_Grid_with_Obstacles_Elimination.java
1 parent 97673fd commit e0cace7

File tree

1 file changed

+61
-0
lines changed

1 file changed

+61
-0
lines changed
Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
class Solution {
2+
private int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
3+
4+
public int shortestPath(int[][] grid, int k) {
5+
int targetRow = grid.length - 1, targetCol = grid[0].length - 1;
6+
7+
Queue<int[]> q = new LinkedList<>();
8+
boolean[][][] visited = new boolean[grid.length][grid[0].length][k + 1];
9+
10+
q.offer(new int[]{0, 0, 0});
11+
visited[0][0][0] = true;
12+
13+
int result = 0;
14+
while (!q.isEmpty()) {
15+
int size = q.size();
16+
17+
for (int i = 0; i < size; i++) {
18+
int[] currStep = q.poll();
19+
20+
int currRow = currStep[0];
21+
int currCol = currStep[1];
22+
int currK = currStep[2];
23+
24+
if (currRow == targetRow && currCol == targetCol) {
25+
return result;
26+
}
27+
28+
for (int[] dir : dirs) {
29+
int nextRow = currRow + dir[0];
30+
int nextCol = currCol + dir[1];
31+
int nextK = currK;
32+
33+
if (!isValidStep(grid, nextRow, nextCol)) {
34+
continue;
35+
}
36+
37+
if (grid[nextRow][nextCol] == 1) {
38+
++nextK;
39+
}
40+
41+
if (nextK <= k && !visited[nextRow][nextCol][nextK]) {
42+
q.offer(new int[]{nextRow, nextCol, nextK});
43+
visited[nextRow][nextCol][nextK] = true;
44+
}
45+
}
46+
}
47+
48+
++result;
49+
}
50+
51+
return -1;
52+
}
53+
54+
private boolean isValidStep(int[][] grid, int row, int col) {
55+
if (row < 0 || col < 0 || row >= grid.length || col >= grid[0].length) {
56+
return false;
57+
}
58+
59+
return true;
60+
}
61+
}

0 commit comments

Comments
 (0)
0