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.
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <unordered_set>
5
6using namespace std;
7
8class Solution {
9public:
10 int minimumTime(vector<vector<int>>& grid) {
11 int m = grid.size(), n = grid[0].size();
12 priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
13 pq.push({0, 0, 0}); // {time, row, col}
14 unordered_set<int> visited;
15 vector<vector<int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
16
17 while (!pq.empty()) {
18 auto current = pq.top(); pq.pop();
19 int t = current[0], r = current[1], c = current[2];
20 int pos = r * n + c;
21 if (r == m - 1 && c == n - 1) return t;
22 if (visited.find(pos) != visited.end()) continue;
23 visited.insert(pos);
24
25 for (const auto& dir : directions) {
26 int new_r = r + dir[0], new_c = c + dir[1];
27 if (new_r >= 0 && new_r < m && new_c >= 0 && new_c < n) {
28 int wait_time = max(0, grid[new_r][new_c] - (t + 1));
29 pq.push({t + 1 + wait_time, new_r, new_c});
30 }
31 }
32 }
33 return -1;
34 }
35};
36
37int main() {
38 Solution sol;
39 vector<vector<int>> grid = {{0,1,3,2},{5,1,2,5},{4,3,8,6}};
40 cout << sol.minimumTime(grid) << endl; // Output: 7
41 return 0;
42}This C++ solution uses a priority queue to manage state transitions, checking and enqueuing next possible nodes while considering the grid's constraints. The priority queue effectively operates based on the minimal next time cost.
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)
1from collections import deque
2
The Python solution applies BFS using a deque structure to simulate levels of operation, maintaining an auxiliary matrix to record the earliest times a cell can be visited, ensuring grid constraints are respected.