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}

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;
}