Sponsored
Sponsored
This approach uses a priority queue to implement a modified version of Dijkstra's algorithm. The challenge here includes managing both the time constraints specified by the grid and the movement cost. The goal is to find the shortest path in terms of time while making sure each cell is entered at a valid time.
We use a priority queue to determine which cell to visit next based on the minimum time it takes to safely visit it. This is similar to choosing the shortest weighted edge in Dijkstra's algorithm, but our 'weight' here is the time passed.
Time Complexity: O(m*n*log(m*n)) due to heap operations for each cell.
Space Complexity: O(m*n) to store the visited set.
1import java.util.PriorityQueue;
2import java.util.HashSet;
3import java.util.Set;
4
5public class MinimumTime {
6 public int minimumTime(int[][] grid) {
7 int m = grid.length;
8 int n = grid[0].length;
9 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
10 pq.offer(new int[]{0, 0, 0}); // (time, row, col)
11 Set<String> visited = new HashSet<>();
12
13 int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
14
15 while (!pq.isEmpty()) {
16 int[] curr = pq.poll();
17 int t = curr[0], r = curr[1], c = curr[2];
18 String pos = r + "," + c;
19 if (pos.equals((m - 1) + "," + (n - 1))) {
20 return t;
21 }
22 if (!visited.add(pos)) continue;
23
24 for (int[] dir : directions) {
25 int new_r = r + dir[0];
26 int new_c = c + dir[1];
27
28 if (new_r >= 0 && new_c >= 0 && new_r < m && new_c < n) {
29 int wait_time = Math.max(0, grid[new_r][new_c] - (t + 1));
30 pq.offer(new int[]{t + 1 + wait_time, new_r, new_c});
31 }
32 }
33 }
34
35 return -1;
36 }
37
38 public static void main(String[] args) {
39 MinimumTime minTime = new MinimumTime();
40 int[][] grid = {{0,1,3,2},{5,1,2,5},{4,3,8,6}};
41 System.out.println(minTime.minimumTime(grid)); // Output: 7
42 }
43}The Java solution follows similar logic to the Python solution, leveraging a priority queue and a set to track visited cells. Each move is evaluated based on its new position and calculated time, considering the grid's wait time.
This approach uses a breadth-first search (BFS) where we evaluate the grid level by level. Instead of using a priority queue, the BFS explores nodes in increasing order of time levels, trying to meet grid constraints at each level. It tracks the earliest time a cell can be safely visited.
Time Complexity: O(m*n)
Space Complexity: O(m*n)
1import java.util.
The Java code uses a regular BFS and tracks the earliest possible time each cell is visited under grid constraints. The LinkedList queue traditionally maintains nodes for level-processing.