列表

详情

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

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

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

 

示例 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 。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int minCost(vector<int>& startPos, vector<int>& homePos, vector<int>& rowCosts, vector<int>& colCosts) { } };

java 解法, 执行用时: 1 ms, 内存消耗: 57.8 MB, 提交时间: 2023-09-17 11:53:13 

class Solution {
    public int minCost(int[] startPos, int[] homePos, int[] rowCosts, int[] colCosts) {
        int minX = Math.min(startPos[0],homePos[0]);
        int minY = Math.min(startPos[1],homePos[1]);
        int maxX = Math.max(startPos[0],homePos[0]);
        int maxY = Math.max(startPos[1],homePos[1]);

        //最小到最大代价全花
        int ans = 0;
        for(int i = minX; i<=maxX; i++){
            ans+=rowCosts[i];
        }

        for(int j = minY; j <= maxY; j++){
            ans+=colCosts[j];
        }

        //起点不需要代价
        ans-=rowCosts[startPos[0]];
        ans-=colCosts[startPos[1]];

        return ans;
    }
}

python3 解法, 执行用时: 84 ms, 内存消耗: 28.3 MB, 提交时间: 2023-09-17 11:52:51 

class Solution:
    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:
        r1, c1 = startPos[0], startPos[1]
        r2, c2 = homePos[0], homePos[1]
        res = 0   # 总代价
        # 移动至家所在行，判断行间移动方向并计算对应代价
        if r2 >= r1:
            for i in range(r1 + 1, r2 + 1):
                res += rowCosts[i]
        else:
            for i in range(r2, r1):
                res += rowCosts[i]
        # 移动至家所在位置，判断列间移动方向并计算对应代价
        if c2 >= c1:
            for i in range(c1 + 1, c2 + 1):
                res += colCosts[i]
        else:
            for i in range(c2, c1):
                res += colCosts[i]
        return res

cpp 解法, 执行用时: 156 ms, 内存消耗: 146.8 MB, 提交时间: 2023-09-17 11:52:30 

class Solution {
public:
    int minCost(vector<int>& startPos, vector<int>& homePos, vector<int>& rowCosts, vector<int>& colCosts) {
        int r1 = startPos[0], c1 = startPos[1];
        int r2 = homePos[0], c2 = homePos[1];
        int res = 0;   // 总代价
        // 移动至家所在行，判断行间移动方向并计算对应代价
        if (r2 >= r1){
            res += accumulate(rowCosts.begin() + r1 + 1, rowCosts.begin() + r2 + 1, 0);
        }
        else{
            res += accumulate(rowCosts.begin() + r2, rowCosts.begin() + r1, 0);
        }
        // 移动至家所在位置，判断列间移动方向并计算对应代价
        if (c2 >= c1){
            res += accumulate(colCosts.begin() + c1 + 1, colCosts.begin() + c2 + 1, 0);
        }
        else{
            res += accumulate(colCosts.begin() + c2, colCosts.begin() + c1, 0);
        }
        return res;
    }
};

golang 解法, 执行用时: 260 ms, 内存消耗: 8.9 MB, 提交时间: 2023-09-17 11:52:01 

/**
 * 由于 rowCosts 和 colCosts 的元素均为非负数，
 * 所以除了径直走以外的其它策略都不可能更优，那么直接统计径直走的代价即可。
 */
func minCost(startPos, homePos, rowCosts, colCosts []int) int {
	x0, y0, x1, y1 := startPos[0], startPos[1], homePos[0], homePos[1]
	ans := -rowCosts[x0] - colCosts[y0] // 初始的行列无需计算
	if x0 > x1 { x0, x1 = x1, x0 } // 交换位置，保证 x0 <= x1
	if y0 > y1 { y0, y1 = y1, y0 } // 交换位置，保证 y0 <= y1
	for _, cost := range rowCosts[x0 : x1+1] { ans += cost } // 统计答案
	for _, cost := range colCosts[y0 : y1+1] { ans += cost } // 统计答案
	return ans
}

上一题

© 2024 leetcode.cn