CSDN竞赛—第69期—深度优先搜索

题目：

二维地图heights，其中heights表示格子(row,col) 的高度。左上角格子(0,0)去右下角的格子 (rows-1, columns-1)，每次可以往上，下，左，右四个方向之一移动，你想要找到H值最小的路径。一条路径的H值是路径上相邻格子之间高度差绝对值的最大值决定的。请你返回从左上角走到右下角的最小H值。

输入：heights = [[1,2,2],[3,8,2],[5,3,5]]

输出：2

算法思路：采用深度优先搜索算法，建立一个访问节点列表，采用递归的思路找路径，然后使用二分法找最小H值，Python代码如下：

def dfs(row,col,heights,visited,mid):
    if row == len(heights)-1 and col == len(heights[0])-1:
        return True
    visited[row][col]=True
    directions=[(0,1),(0,-1),(1,0),(-1,0)]
    for dr,dc in directions:
        new_row,new_col = row+dr, col+dc
        if 0<=new_row<len(heights) and 0<=new_col<len(heights[0]) and not visited[new_row][new_col]:
            if abs(heights[new_row][new_col]-heights[row][col])<=mid:
                if dfs(new_row,new_col,heights,visited,mid):
                    return True
    return False
 
def minimun_max_height(heights):
    left,right = 0,max(map(max,heights))
    while left < right:
        mid = (left+right)//2
        visited = [[False]*len(heights[0]) for _ in range(len(heights))]
        if dfs(0,0,heights,visited,mid):
            right = mid
        else:
            left = mid+1
    return left
 
if __name__ == "__main__":
    heights = eval(input())
    result = minimun_max_height(heights)
    print(result)