网格图中机器人回家的最小代价

标签: 贪心 数组

难度: Medium

给你一个 m x n 的网格图，其中 (0, 0) 是最左上角的格子，(m - 1, n - 1) 是最右下角的格子。给你一个整数数组 startPos ，startPos = [startrow, startcol] 表示 初始 有一个 机器人 在格子 (startrow, startcol) 处。同时给你一个整数数组 homePos ，homePos = [homerow, homecol] 表示机器人的 家 在格子 (homerow, homecol) 处。

机器人需要回家。每一步它可以往四个方向移动：上，下，左，右，同时机器人不能移出边界。每一步移动都有一定代价。再给你两个下标从 0 开始的额整数数组：长度为 m 的数组 rowCosts  和长度为 n 的数组 colCosts 。

  • 如果机器人往 上 或者往 下 移动到第 r 行 的格子，那么代价为 rowCosts[r] 。
  • 如果机器人往 左 或者往 右 移动到第 c 列 的格子，那么代价为 colCosts[c] 。

请你返回机器人回家需要的 最小总代价 。

示例 1：

输入：startPos = [1, 0], homePos = [2, 3], rowCosts = [5, 4, 3], colCosts = [8, 2, 6, 7]
输出：18
解释：一个最优路径为：
从 (1, 0) 开始
-> 往下走到 (2, 0) 。代价为 rowCosts[2] = 3 。
-> 往右走到 (2, 1) 。代价为 colCosts[1] = 2 。
-> 往右走到 (2, 2) 。代价为 colCosts[2] = 6 。
-> 往右走到 (2, 3) 。代价为 colCosts[3] = 7 。
总代价为 3 + 2 + 6 + 7 = 18

示例 2：

输入：startPos = [0, 0], homePos = [0, 0], rowCosts = [5], colCosts = [26]
输出：0
解释：机器人已经在家了，所以不需要移动。总代价为 0 。

提示：

  • m == rowCosts.length
  • n == colCosts.length
  • 1 <= m, n <= 105
  • 0 <= rowCosts[r], colCosts[c] <= 104
  • startPos.length == 2
  • homePos.length == 2
  • 0 <= startrow, homerow < m
  • 0 <= startcol, homecol < n

Submission

运行时间: 49 ms

内存: 28.0 MB

class Solution:
    def minCost(
        self,
        startPos: List[int],
        homePos: List[int],
        rowCosts: List[int],
        colCosts: List[int],
    ) -> int:
        i, j = startPos
        x, y = homePos
        ans = 0
        if i < x:
            ans += sum(rowCosts[i + 1 : x + 1])
        else:
            ans += sum(rowCosts[x:i])
        if j < y:
            ans += sum(colCosts[j + 1 : y + 1])
        else:
            ans += sum(colCosts[y:j])
        return ans

Explain

此题解通过直接计算从起始位置到目标位置的行和列移动代价来解决问题。首先，将起始位置 (startPos) 和目标位置 (homePos) 分别分解为行和列的坐标。接着，根据行和列坐标的相对位置（是否需要向上或向下、向左或向右移动），计算行和列的代价。如果目标行在起始行的下方，累加从起始行到目标行之间的所有行代价；如果在上方，则累加从目标行到起始行的行代价。列的处理方法相同。最后，将行和列的代价相加得到总代价。

时间复杂度: O(m + n)

空间复杂度: O(1)

class Solution:
    def minCost(
        self,
        startPos: List[int],
        homePos: List[int],
        rowCosts: List[int],
        colCosts: List[int],
    ) -> int:
        i, j = startPos  # 起始位置的行和列
        x, y = homePos   # 目标位置的行和列
        ans = 0           # 初始化总代价为0
        if i < x:
            ans += sum(rowCosts[i + 1 : x + 1])  # 如果目标行在下方，累加行代价
        else:
            ans += sum(rowCosts[x:i])          # 如果目标行在上方，累加行代价
        if j < y:
            ans += sum(colCosts[j + 1 : y + 1])  # 如果目标列在右方，累加列代价
        else:
            ans += sum(colCosts[y:j])          # 如果目标列在左方，累加列代价
        return ans  # 返回计算得到的总代价

Explore

题解中使用`rowCosts[i + 1 : x + 1]`而不是`rowCosts[i:x]`是因为行代价`rowCosts[i]`代表的是从第`i`行移动到第`i+1`行的代价。因此，如果机器人从行`i`移动到行`x`，则需要从`i+1`行开始计算移动代价，直到`x`行，故取`i+1`到`x+1`的切片来确保包括从`i`到`x`的所有移动代价。

列代价的计算类似于行代价。`colCosts[j]`代表从第`j`列移动到第`j+1`列的代价。当使用`colCosts[j + 1 : y + 1]`累加时，意味着从第`j`列出发的移动代价不包括在内，因为这代表的是从`j+1`列开始到`y`列的移动。如果机器人从列`j`向列`y`移动，其实是从`j`列的下一列开始计算代价，所以初始单元格的列代价并不需要被考虑。

如果起始位置和目标位置在同一行或同一列，比如完全相同的情况，此方法仍然有效。在这种情况下，行或列的切片操作将返回一个空列表，例如`rowCosts[x:x]`或`colCosts[y:y]`，其结果是`sum`函数将返回0。因此，总代价将为0，这符合预期，因为机器人无需移动。

在本题解中，假设的是机器人移动的行和列代价是固定的，并且只与移动的行列位置有关，不依赖于其他路径选择。因此，题解采取了直接计算从起始位置到目标位置的最短路径代价的简单方法。如果行和列的代价变化不仅取决于移动的行列，而且与具体的路径选择有关，则需要考虑更复杂的路径规划算法，如动态规划或Dijkstra算法来找到最低代价的路径。