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.
1from collections import deque
2
3def shortestPath(grid, k):
4 m, n = len(grid), len(grid[0])
5 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
6 queue = deque([(0, 0, 0, 0)])
7 visited = [[[False] * (k + 1) for _ in range(n)] for _ in range(m)]
8 visited[0][0][0] = True
9 while queue:
10 x, y, steps, remaining_k = queue.popleft()
11 if x == m - 1 and y == n - 1:
12 return steps
13 for dx, dy in directions:
14 nx, ny = x + dx, y + dy
15 if 0 <= nx < m and 0 <= ny < n:
16 new_k = remaining_k + grid[nx][ny]
17 if new_k <= k and not visited[nx][ny][new_k]:
18 visited[nx][ny][new_k] = True
19 queue.append((nx, ny, steps + 1, new_k))
20 return -1In the Python solution, we initiate a queue to perform BFS and a visited array to track visited states. Each state contains the (x, y) position, number of steps taken, and the number of obstacles removed. For each state, we try moving in four directions and push valid states into the queue.
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 shortestPath
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).