1. 最小最大值问题，二分答案搜索
2. heights的最大值为10⁶，所以右边界为10⁶，左边界为0，通过dfs来判断是否存在一条路径，其中所有的相邻格子的高度差绝对值小于左右边界的中点

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        l, r = 0, 10**6 - 1
        vis = set()
        def dfs(i, j, m):
            if (i, j) in vis:
                return False
            if i == len(heights) - 1 and j == len(heights[0]) - 1:
                return True
            vis.add((i, j))
            if i + 1 < len(heights) and abs(heights[i + 1][j] - heights[i][j]) <= m:
                if dfs(i + 1, j, m):
                    return True
            if i - 1 >= 0 and abs(heights[i - 1][j] - heights[i][j]) <= m:
                if dfs(i - 1, j, m):
                    return True
            if j + 1 < len(heights[0]) and abs(heights[i][j + 1] - heights[i][j]) <= m:
                if dfs(i, j + 1, m):
                    return True
            if j - 1 >= 0 and abs(heights[i][j - 1] - heights[i][j]) <= m:
                if dfs(i, j - 1, m):
                    return True
            return False

        while l < r:
            vis.clear()
            m = (l + r) >> 1
            if dfs(0, 0, m):
                r = m
            else:
                l = m + 1
        
        return l