Sponsored
Sponsored
This approach utilizes Breadth-First Search (BFS) to explore paths in the grid, while maintaining a state that includes the current position and number of obstacles removed. We can advance through the grid using BFS, and track paths using a queue where each entry consists of a tuple containing the current position, number of steps taken, and the number of obstacles removed. A three-dimensional list keeps track of states visited at any position with a particular obstacle count to avoid unnecessary reprocessing.
The time complexity is O(m * n * k) because we process each cell at most k times (once for each possible count of removed obstacles). The space complexity is also O(m * n * k) due to the visited array used for tracking states.
1import java.util.LinkedList;
2import java.util.Queue;
3
4public class ShortestPath {
5 public int shortestPath(int[][] grid, int k) {
6 int m = grid.length, n = grid[0].length;
7 boolean[][][] visited = new boolean[m][n][k + 1];
8 Queue<int[]> queue = new LinkedList<>();
9 queue.add(new int[]{0, 0, 0, 0});
10 visited[0][0][0] = true;
11
12 int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
13
14 while (!queue.isEmpty()) {
15 int[] curr = queue.poll();
16 int x = curr[0], y = curr[1], steps = curr[2], obstacles = curr[3];
17
18 if (x == m - 1 && y == n - 1) return steps;
19
20 for (int[] d : directions) {
21 int nx = x + d[0], ny = y + d[1];
22 if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
23 int newObstacles = obstacles + grid[nx][ny];
24 if (newObstacles <= k && !visited[nx][ny][newObstacles]) {
25 visited[nx][ny][newObstacles] = true;
26 queue.add(new int[]{nx, ny, steps + 1, newObstacles});
27 }
28 }
29 }
30 }
31 return -1;
32 }
33}The Java implementation follows the same BFS procedure, using a Queue to explore possible paths. Each node in the queue stores its current coordinates, step count, and obstacles removed, and we advance through valid moves by checking unobstructed or removable paths.
A* Search is an informed search algorithm, which is often used in pathfinding and graph traversal. For this grid problem, we use a priority queue to explore paths, using a heuristic function. The heuristic can be the Manhattan distance to the target minus the remaining k value, incentivizing routes closer to the target with lesser obstacle removals.
The time complexity is generally higher than BFS due to the additional computation for the heuristic, but edges are still cut off through pruning. The space complexity remains similar to the previous method because of visited state cache retention.
1import heapq
2
3def
Leveraging a priority queue for A* search, this Python solution uses a heuristic to decide which paths to explore first. We prioritize paths by their distance to the target, pushing the states into the queue with both the actual cost (steps traveled) and the estimated cost (heuristic).