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.
1var minimumTime = function(grid) {
2 const m = grid.length, n = grid[0].length;
3 const pq = new MinPriorityQueue({priority: (x) => x[0]});
4 pq.enqueue([0, 0, 0]); // [time, row, col]
5 const visited = new Set();
6 const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
7
8 while (!pq.isEmpty()) {
9 const [t, r, c] = pq.dequeue().element;
10 if (r === m - 1 && c === n - 1) return t;
11 if (visited.has(`${r},${c}`)) continue;
12 visited.add(`${r},${c}`);
13
14 for (let [dr, dc] of directions) {
15 const new_r = r + dr;
16 const new_c = c + dc;
17 if (new_r >= 0 && new_r < m && new_c >= 0 && new_c < n && !visited.has(`${new_r},${new_c}`)) {
18 const wait_time = Math.max(0, grid[new_r][new_c] - (t + 1));
19 pq.enqueue([t + 1 + wait_time, new_r, new_c]);
20 }
21 }
22 }
23 return -1;
24};
25
26// Example usage
27console.log(minimumTime([[0,1,3,2],[5,1,2,5],[4,3,8,6]])); // Output: 7The JavaScript solution employs a MinPriorityQueue data structure to prioritize nodes by their minimal time cost. A set is utilized to track visited states and prevent redundant checks.
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)
1#include <iostream>
2#include <vector>
3#include <queue>
#include <climits>
using namespace std;
class Solution {
public:
int minimumTime(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
queue<vector<int>> queue;
vector<vector<int>> earliest(m, vector<int>(n, INT_MAX));
earliest[0][0] = 0;
queue.push({0, 0, 0}); // {time, row, col}
vector<pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!queue.empty()) {
auto current = queue.front(); queue.pop();
int t = current[0], r = current[1], c = current[2];
if (r == m - 1 && c == n - 1) return t;
for (const auto& dir : directions) {
int new_r = r + dir.first, new_c = c + dir.second;
if (new_r >= 0 && new_r < m && new_c >= 0 && new_c < n) {
int wait_time = max(0, grid[new_r][new_c] - (t + 1));
int next_time = t + 1 + wait_time;
if (next_time < earliest[new_r][new_c]) {
earliest[new_r][new_c] = next_time;
queue.push({next_time, new_r, new_c});
}
}
}
}
return -1;
}
};
int main() {
Solution sol;
vector<vector<int>> grid = {{0,2,4},{3,2,1},{1,0,4}};
cout << sol.minimumTime(grid) << endl; // Output: -1
return 0;
}The C++ solution employs a standard BFS level traversal. It maintains an auxiliary matrix to store the earliest time that each cell can be visited due to grid constraints, performing checks on all four directional moves.