import heapq

class Solution:
    def minimumEffortPath(self, matrix):
        # 如果矩阵为空或者矩阵的第一行为空，则返回0
        if not matrix or not matrix[0]:
            return 0
        
        # 获取矩阵的行数和列数
        rows, cols = len(matrix), len(matrix[0])
        # 定义四个方向：右、左、下、上
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        # 初始化堆，元素为 (effort, row, col)，表示代价、行、列
        heap = [(0, 0, 0)]
        # 记录已访问过的位置
        visited = set([(0, 0)])
        
        while heap:
            # 弹出堆中的最小元素
            effort, row, col = heapq.heappop(heap)
            
            # 如果到达终点，返回当前代价
            if row == rows – 1 and col == cols – 1:
                return effort
            
            # 遍历四个方向
            for dx, dy in directions:
                new_row, new_col = row + dx, col + dy
                # 判断新位置是否合法且未访问过
                if 0 <= new_row < rows and 0 <= new_col < cols and (new_row, new_col) not in visited:
                    # 计算新位置的代价
                    new_effort = max(effort, abs(matrix[row][col] – matrix[new_row][new_col]))
                    # 将新位置的信息加入堆和已访问集合
                    heapq.heappush(heap, (new_effort, new_row, new_col))
                    visited.add((new_row, new_col))
        
        return -1  # 如果没有找到路径（对于这个问题来说不应该发生）

# Solution.py结束

代码在测试[[1,2,2],[3,8,2],[5,3,5]]有误  输出3   可以提交通过