Path With Minimum Effort time out when using Bellman Ford?

111

I tried to solve the Path With Minimum Effort time out when using optimized Bellman Ford taught in the Graph Card. However, it times out... I means it kinds of make sense since time complexity is O((n*m)^2). But is there a way that I can use Bellman Ford for this problem? I means I wonder why this question is put there in the first place if bellman ford is not going to work. My code is attached below (C++).

class Solution {
    int n;
    int m;
    vector<vector<int>> dirs = {{-1,0},{1,0},{0,1},{0,-1}};
    bool check(int i,int j){
        return i>=0&&j>=0&&i<n&&j<m;
    }
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        n = heights.size();
        if(n==0) return 0;
        m = heights[0].size();
        vector<vector<int>> prev(n,vector<int>(m,INT_MAX));
        vector<vector<int>> cur(n,vector<int>(m,INT_MAX));
        prev[0][0] = 0;
        cur[0][0] = 0;
        int cnt = n*m-1;
        bool hasUpdate = true;
        while(hasUpdate&&cnt>0){
            hasUpdate = false;
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    for(auto const & dir:dirs){
                        int fx = i + dir[0];
                        int fy = j + dir[1];
                        if(check(fx,fy)&&prev[fx][fy]!=INT_MAX) cur[i][j] = min(cur[i][j],max(prev[fx][fy], abs(heights[i][j]-heights[fx][fy])));
                    }
                    if(prev[i][j]!=cur[i][j]) hasUpdate = true;
                }
            }
            prev = cur;
            cnt--;
        }
        return prev[n-1][m-1];
    }
};

Comments (1)