class Solution {
public:
    bool dfs(vector<vector<int>>& heights, int r, int c, int currEffort, int& minEffort, vector<vector<int>>& visited) {
        int N = heights.size();
        int M = heights[0].size();
        visited[r][c] = 1;

        // Check if reached the destination
        if (r == N - 1 && c == M - 1) {
            minEffort = min(minEffort, currEffort);
            return true;
        }

        vector<pair<int, int>> dirs = {{r+1, c}, {r-1, c}, {r, c-1}, {r, c+1}};
        for (auto dir : dirs) {
            int rn = dir.first;
            int cn = dir.second;
            // Check validity
            if (rn >= 0 && rn < N && cn >= 0 && cn < M && visited[rn][cn] == 0) {
                int nextEffort = abs(heights[rn][cn] - heights[r][c]);
                int newEffort = max(currEffort, nextEffort);

                // Prune if the new effort is already higher than the minimum effort found so far
                if (newEffort >= minEffort)
                    continue;

                if (dfs(heights, rn, cn, newEffort, minEffort, visited)) {
                    // If the path is found, return immediately
                    return true;
                }
            }
        }

        return false;
    }

    int minimumEffortPath(vector<vector<int>>& heights) {
        int rows = heights.size();
        int cols = heights[0].size();
        vector<vector<int>> visited(rows, vector<int>(cols, 0));
        int minEffort = INT_MAX;
        dfs(heights, 0, 0, 0, minEffort, visited);
        return minEffort;
    }
};