自行车炫技赛场

难度: Medium

「力扣挑战赛」中 `N*M` 大小的自行车炫技赛场的场地由一片连绵起伏的上下坡组成，场地的高度值记录于二维数组 `terrain` 中，场地的减速值记录于二维数组 `obstacle` 中。 - 若选手骑着自行车从高度为 `h1` 且减速值为 `o1` 的位置到高度为 `h2` 且减速值为 `o2` 的相邻位置（上下左右四个方向），速度变化值为 `h1-h2-o2`（负值减速，正值增速）。选手初始位于坐标 `position` 处且初始速度为 1，请问选手可以刚好到其他哪些位置时速度依旧为 1。请以二维数组形式返回这些位置。若有多个位置则按行坐标升序排列，若有多个位置行坐标相同则按列坐标升序排列。 **注意：** 骑行过程中速度不能为零或负值 **示例 1：** > 输入：`position = [0,0], terrain = [[0,0],[0,0]], obstacle = [[0,0],[0,0]]` > > 输出：`[[0,1],[1,0],[1,1]]` > > 解释： > 由于当前场地属于平地，根据上面的规则，选手从`[0,0]`的位置出发都能刚好在其他处的位置速度为 1。 **示例 2：** > 输入：`position = [1,1], terrain = [[5,0],[0,6]], obstacle = [[0,6],[7,0]]` > > 输出：`[[0,1]]` > > 解释： > 选手从 `[1,1]` 处的位置出发，到 `[0,1]` 处的位置时恰好速度为 1。 **提示：** - `n == terrain.length == obstacle.length` - `m == terrain[i].length == obstacle[i].length` - `1 <= n <= 100` - `1 <= m <= 100` - `0 <= terrain[i][j], obstacle[i][j] <= 100` - `position.length == 2` - `0 <= position[0] < n` - `0 <= position[1] < m`

Submission

运行时间: 43 ms

内存: 16.8 MB

class Solution:
    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:
        res = []
        m, n = len(terrain), len(terrain[0])
        a = [(position[0], position[1], 1)]
        s = {(position[0], position[1], 1)}
        i = 0
        while i < len(a):
            r, c, speed = a[i]
            i += 1
            for rr, cc in [(r-1, c), (r, c-1), (r+1, c), (r, c+1)]:
                if 0 <= rr < m and 0 <= cc < n:
                    speed_new = speed + terrain[r][c] - terrain[rr][cc] - obstacle[rr][cc]
                    if speed_new > 0 and (rr, cc, speed_new) not in s:
                        s.add((rr, cc, speed_new))
                        a.append((rr, cc, speed_new))
                        if speed_new == 1:
                            res.append([rr, cc])
        res.sort()
        return res

Explain

题解采用了宽度优先搜索（BFS）的策略来寻找所有可能的速度为1的位置。初始位置及速度被加入队列，并通过一个集合来防止重复访问相同的状态（位置和速度）。从队列中取出当前位置，遍历四个可能的移动方向（上、下、左、右）。对于每一个合法的新位置，计算新的速度，若速度大于0且该状态未被访问过，则加入队列继续搜索。如果新的速度恰好为1，该位置则加入结果列表。最后，结果按要求排序后返回。

时间复杂度: O(N*M*V)

空间复杂度: O(N*M*V)

class Solution:
    def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:
        res = []  # 结果列表，存放速度恰好为1的位置
        m, n = len(terrain), len(terrain[0])  # 赛场的行数和列数
        a = [(position[0], position[1], 1)]  # BFS队列，存储位置和速度的元组
        s = {(position[0], position[1], 1)}  # 集合，用于检查是否重复访问
        i = 0  # 队列索引
        while i < len(a):  # BFS主循环
            r, c, speed = a[i]  # 取出当前位置和速度
            i += 1
            for rr, cc in [(r-1, c), (r, c-1), (r+1, c), (r, c+1)]:  # 遍历四个可能的方向
                if 0 <= rr < m and 0 <= cc < n:  # 确保新位置在界内
                    speed_new = speed + terrain[r][c] - terrain[rr][cc] - obstacle[rr][cc]  # 计算新速度
                    if speed_new > 0 and (rr, cc, speed_new) not in s:  # 如果速度合法且未访问过
                        s.add((rr, cc, speed_new))  # 标记为已访问
                        a.append((rr, cc, speed_new))  # 加入队列
                        if speed_new == 1:  # 如果速度恰好为1
                            res.append([rr, cc])  # 加入结果列表
        res.sort()  # 对结果排序
        return res  # 返回排序后的结果

Explore

在本题中，速度变化为负值意味着自行车无法继续前进，因为速度不能小于或等于零。因此，当计算出的新速度`speed_new`为负或零时，这个新状态不会被加入队列进行进一步的搜索。这是因为速度为负或零意味着自行车停止运动，不再具有继续探索其他位置的能力。只有当`speed_new`大于零时，该状态才可能继续前进，并且有可能达到其他的速度为1的位置。

在这个问题中，使用宽度优先搜索（BFS）是为了确保在探索所有可能的位置和速度组合时，可以更均匀和系统地遍历各个可能的状态。BFS通过逐层探索所有可能的移动，帮助确保找到所有速度恰好为1的位置。相比之下，深度优先搜索（DFS）可能会导致算法过早地深入一个方向，从而可能错过更近的、速度为1的位置。此外，BFS在处理状态空间搜索问题时通常更容易管理和预测性能，特别是当状态空间较大时。

在这个题解当中，速度为零的情况不被考虑加入队列，是因为速度为零意味着自行车已经停止，不能继续前进到任何新的位置。这与题目的要求相违背，因为目标是探索从初始位置开始，速度恰好再次变为1时的可达位置。如果速度为零，则无法继续探索，也就无法达到速度再次为1的状态。因此，只有当速度大于零时，才能继续探索并可能找到符合条件的位置。