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.
1using System;
2using System.Collections.Generic;
3
4public class GridPath {
public int ShortestPath(int[][] grid, int k) {
int m = grid.Length, n = grid[0].Length;
int[][] directions = new int[][] { new int[] {0, 1}, new int[] {1, 0}, new int[] {0, -1}, new int[] {-1, 0} };
var comparer = Comparer<(int f, int steps, int x, int y, int obstacles)>.Create((a, b) => a.f.CompareTo(b.f));
SortedSet<(int f, int steps, int x, int y, int obstacles)> pq = new SortedSet<(int, int, int, int, int)>(comparer);
pq.Add((0 + m - 1 + n - 1, 0, 0, 0, 0));
int[][] visited = new int[m][];
for (int i = 0; i < m; ++i) { visited[i] = new int[n]; Array.Fill(visited[i], int.MaxValue); }
visited[0][0] = 0;
while (pq.Count > 0) {
var top = pq.Min;
pq.Remove(top);
int steps = top.steps, x = top.x, y = top.y, obstacles = top.obstacles;
if (x == m - 1 && y == n - 1) return steps;
foreach (var dir in directions) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
int new_obstacles = obstacles + grid[nx][ny];
if (new_obstacles < visited[nx][ny] && new_obstacles <= k) {
visited[nx][ny] = new_obstacles;
pq.Add((steps + 1 + m - 1 - nx + n - 1 - ny, steps + 1, nx, ny, new_obstacles));
}
}
}
}
return -1;
}
}The C# solution employs a SortedSet to function as a priority queue for A* search. Nodes are compared using both current path cost (steps) and expected cost from heuristic estimates. This balances exploring close and effective paths while keeping memory checks efficient.