2087.网格图中机器人回家的最小代价：脑筋急转弯（固定走法）

【LetMeFly】2087.网格图中机器人回家的最小代价：脑筋急转弯（固定走法）

力扣题目链接：https://leetcode.cn/problems/minimum-cost-homecoming-of-a-robot-in-a-grid/

给你一个 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

解题方法：脑筋急转弯（固定走法）

想想我们是怎么计算代价的，如果上下移动到了某一行，不论是在哪一列移动到的，都加上这一行的“代价”；列同理。

假设起点终点不在同一行，那么竖直方向上从起点到终点的移动是不可避免的。并且我们没有必要往上移动后再往下移动这样来回绕路；竖直方向同理。

也就是说，任何场景我们都直接像样例中那样一个L形路径走过去就行了。

• 时间复杂度$\mathcal{O}(|start_{row} - home_{row}| + |start_{col} - home_{col}|)$
• 空间复杂度$\mathcal{O}(1)$，前提是不使用python普通切片改为循环

AC代码

C++

$(起点, 终点]$

/*
 * @LastEditTime: 2026-04-04 14:05:23
 */
class Solution {
public:
    int minCost(vector<int>& startPos, vector<int>& homePos, vector<int>& rowCosts, vector<int>& colCosts) {
        int ans = 0;
        for (int from = startPos[0], to = homePos[0], direction = to > from ? 1 : -1; from != to; from += direction) {
            ans += rowCosts[from + direction];
        }
        for (int from = startPos[1], to = homePos[1], direction = to > from ? 1 : -1; from != to; from += direction) {
            ans += colCosts[from + direction];
        }
        return ans;
    }
};

Python

$[起点, 终点] - 起点$

'''
LastEditTime: 2026-04-04 14:10:12
'''
from typing import List

class Solution:
    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:
        sx, sy = startPos
        ex, ey = homePos
        return sum(rowCosts[min(sx, ex) : max(sx, ex) + 1]) + sum(colCosts[min(sy, ey) : max(sy, ey) + 1]) - rowCosts[sx] - colCosts[sy]

python切片会拷贝不可变元素

>>> a = [1, 2, 3, 4]
>>> b = a[1:3]
>>> print(b)
[2, 3]
>>> b[0] = 0
>>> print(b)
[0, 3]
>>> print(a)
[1, 2, 3, 4]

啥都没说系列

虽说是固定走法，但其实是固定中又偏自由的走法。
可先左再下，也可先下再左，也可一左一下，反正拐弯不要钱，只要别同时存在往左和往右就好了。

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源