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