2023华为od机试 Python 【路径步数】

傷城~ 2024-03-08 08:41 129阅读 0赞

### 题目 ###

小明喜欢户外运动，这个周末他打算去附近的山区探险，他面前有一张特殊的地图来帮助他找到这片区域的最高点。

这张地图是一个由数字构成的网格。网格中的每一个单元格包含一个数字，代表那个点的高度。其中，数字 0 代表平地，而数字 1 到 9 则代表不同的高度。小明可以向上下左右任何一个方向移动到相邻的单元格中。

然而，小明不是超人，他不能一下子爬得太高或者降得太低。他每次能够爬升或下降的高度差是有限制的，他能够克服的最大高度差是 k。

现在小明站在地图的左上角（0,0 位置），他想知道：

在他的爬升和下降限制下，他能够到达的最高点是多少？  
到达那个点需要多少步？

输入描述  
第一行包含三个整数，分别是 m、n 和 k。其中 m 和 n 代表地图的行数和列数，k 代表小明可以克服的最大高度差。  
接下来的 m 行每行包含 n 个整数，描述了整个地图的高度信息。  
输出描述  
输出两个整数，分别表示：  
小明可以到达的最高点的高度。  
到达那个最高点所需要的最少步数。  
如果小明无法到达任何一个点，那么输出 0 0。

示例  
输入

5 4 1  
0 1 2 0  
1 0 0 0  
1 0 1 2  
1 3 1 0  
0 0 0 9

输出

2 2

解释

根据地图，小明可以到达的最高点是 (0,2) 位置，高度为 2。他可以通过下面的路径到达那里：

(0,0) → (0,1) → (0,2)  
这条路径包含 2 步。

### 代码 ###

def main():
        m, n, k = 5, 4, 1
        grid = [
            [0, 1, 2, 0],
            [1, 0, 0, 0],
            [1, 0, 1, 2],
            [1, 3, 1, 0],
            [0, 0, 0, 9],
        ]
    
        VISITED = 15
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        
        height_to_steps = {
        grid[0][0]: 0}
    
        def dfs(x, y, step):
            prev_height = grid[x][y]
    
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n:
                    curr_height = grid[nx][ny]
                    if abs(curr_height - prev_height) <= k:
                        step += 1
    
                        # 更新当前高度的最小步数
                        if curr_height not in height_to_steps or height_to_steps[curr_height] > step:
                            height_to_steps[curr_height] = step
    
                        grid[x][y] = VISITED
                        dfs(nx, ny, step)
    
                        # 回溯
                        grid[x][y] = prev_height
                        step -= 1
    
        # 从 (0, 0) 位置开始
        dfs(0, 0, 0)
    
        if len(height_to_steps) == 1 and 0 in height_to_steps:
            print("0 0")
            return
    
        # 寻找最高的山峰和对应的最小步数
        max_height = max(height_to_steps.keys())
        min_steps = height_to_steps[max_height]
    
        print(f"{
          max_height} {
          min_steps}")
    
    main()