2577.cpp (1168B)
1 class Solution { 2 public: 3 int minimumTime(vector<vector<int>> &grid) const { 4 const int n = size(grid), m = size(grid[0]); 5 6 static const int offset[] = {-1, 0, 1, 0, -1}; 7 const auto is_valid = [&](const int x, const int y) { 8 return x >= 0 && x < n && y >= 0 && y < m && grid[x][y] >= 0; 9 }; 10 11 using type_t = tuple<int, int, int>; 12 priority_queue<type_t, vector<type_t>, greater<>> pq; 13 14 if (grid[0][1] > 1 && grid[1][0] > 1) return -1; 15 for (pq.emplace(0, 0, 0); !pq.empty();) { 16 const auto [time, a, b] = pq.top(); 17 pq.pop(); 18 19 if (a == n - 1 && b == m - 1) return time; 20 21 for (int k = 0; k < 4; k++) { 22 const int x = a + offset[k + 1]; 23 const int y = b + offset[k]; 24 25 if (!is_valid(x, y)) continue; 26 27 const int req = grid[x][y]; 28 if (time + 1 >= req) 29 pq.emplace(time + 1, x, y); 30 else 31 pq.emplace(req + !((req - time) % 2), x, y); 32 33 grid[x][y] = -1; 34 } 35 } 36 37 return -1; 38 } 39 };