leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2577.cpp (1168B)

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