Description

Submission

class Solution {
    vector<vector<int>> dp;
    int nRow;
    int nCol;
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        nRow = heights.size();
        nCol = heights[0].size();
        
        dp.resize(nRow);
        for(int i = 0; i < nRow; ++i) {
            dp[i].resize(nCol);
            for(int j = 0; j < nCol; ++j) {
                dp[i][j] = INT_MAX / 2;
            }
        }
        
        dp[0][0] = 0;
        
        for(int t = 0; t < nRow * nCol; ++t) {
            bool updated = false;
            for(int x = 0; x < nRow; ++x) {
                for(int y = 0; y < nCol; ++y) {
                    if(x == 0 && y == 0) continue;
                    int height = heights[x][y];
                    int prevDp = dp[x][y];
                    dp[x][y] = min(min(max(getDp(x-1, y, heights), abs(height - getHeight(x-1, y, heights))), 
                          max(getDp(x, y-1, heights), abs(height - getHeight(x, y-1, heights)))), 
                       min(max(getDp(x+1, y, heights), abs(height - getHeight(x+1, y, heights))),
                          max(getDp(x, y+1, heights), abs(height - getHeight(x, y+1, heights)))));
                    //cout << x << " " << y << " " << dp[x][y] << endl;
                    if(prevDp != dp[x][y]) updated = true;
                }
            }
            if(!updated) break;
        }
        return dp[nRow-1][nCol-1];
    }
    
    int getHeight(int x, int y, vector<vector<int>>& heights) {
        if(x < 0 || y < 0 || x >= nRow || y >= nCol) return INT_MAX/2;
        return heights[x][y];
    }
    
    int getDp(int x, int y, vector<vector<int>>& heights) {
        if(x < 0 || y < 0 || x >= nRow || y >= nCol) return INT_MAX/2;
        return dp[x][y];
    }
};