leetcode

Solution to some Leetcode problems written in C++

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

1631.cpp (1072B)

0 class Solution { 1 typedef tuple<unsigned, uint8_t, uint8_t> tile; 2 3 public: 4 int minimumEffortPath(const vector<vector<int>> &heights) { 5 static unsigned efforts[101][101]; 6 const int n = heights.size(), m = heights[0].size(); 7 static const int dirs[5] = {-1, 0, 1, 0, -1}; 8 9 memset(efforts, 0xFF, sizeof(efforts)); 10 priority_queue<tile, vector<tile>, greater<tile>> pq; 11 12 pq.push({0, 0, 0}); 13 while (!pq.empty()) { 14 const auto [effort, x, y] = pq.top(); 15 pq.pop(); 16 17 if (x == n - 1 && y == m - 1) return effort; 18 19 for (int k = 0; k < 4; k++) { 20 const int i = x + dirs[k], j = y + dirs[k + 1]; 21 if (i < 0 || i >= n || j < 0 || j >= m) continue; 22 const unsigned crnt = max(effort, (unsigned)abs(heights[x][y] - heights[i][j])); 23 if (crnt < efforts[i][j]) { 24 efforts[i][j] = crnt; 25 pq.push({crnt, i, j}); 26 } 27 } 28 } 29 30 return -1; 31 } 32 };