2023华为od机试 Python 【路径步数】 傷城~ 2024-03-08 08:41 50阅读 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()
还没有评论，来说两句吧...