Time Cost

28min1s

Implementation

On my first attempt, I only assume the solution would only contain right-move and down-move option. As a result, on my second attempt, I added all four directions and got passed.

Code

• My Solution

  class Solution {
    using PIP = pair<int, pair<int, int>>;
    using PII = pair<int, int>;
  public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        int rows = heights.size(), cols = heights[0].size();
        vector<vector<int>> eff(rows, vector<int>(cols, INT_MAX));
        vector<vector<bool>> v(rows, vector<bool>(cols, false));
        priority_queue<PIP, vector<PIP>, greater<PIP>> q;
        eff[0][0] = 0;
        q.emplace(0, PII{0, 0});
  
        while (!q.empty()) {
            auto [x, yz] = q.top();
            q.pop();
            auto [y, z] = yz;
  
            if (y == rows-1 && z == cols-1) {
                return x;
            }
  
            if (v[y][z]) {
                continue;
            }
            v[y][z] = 1;
  
            if (z != cols-1) {
                // able to move right
                if (max(abs(heights[y][z]-heights[y][z+1]), eff[y][z]) < eff[y][z+1]) {
                    eff[y][z+1] = max(abs(heights[y][z]-heights[y][z+1]), eff[y][z]);
                    q.emplace(eff[y][z+1], PII{y, z+1});
                }
            }
            if (y != rows-1) {
                // able to move down
                if (max(abs(heights[y][z]-heights[y+1][z]), eff[y][z]) < eff[y+1][z]) {
                    eff[y+1][z] = max(abs(heights[y][z]-heights[y+1][z]), eff[y][z]);
                    q.emplace(eff[y+1][z], PII{y+1, z});
                }
            }
            if (z != 0) {
                // able to move left
                if (max(abs(heights[y][z]-heights[y][z-1]), eff[y][z]) < eff[y][z-1]) {
                    eff[y][z-1] = max(abs(heights[y][z]-heights[y][z-1]), eff[y][z]);
                    q.emplace(eff[y][z-1], PII{y, z-1});
                }
            }
            if (y != 0) {
                // able to move top
                if (max(abs(heights[y][z]-heights[y-1][z]), eff[y][z]) < eff[y-1][z]) {
                    eff[y-1][z] = max(abs(heights[y][z]-heights[y-1][z]), eff[y][z]);
                    q.emplace(eff[y-1][z], PII{y-1, z});
                }
            }
        }
  
        return INT_MAX;
    }
  };