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

题目描述

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

机器人需要回家。每一步它可以往四个方向移动：上，下，左，右，同时机器人不能移出边界。每一步移动都有一定代价。再给你两个下标从 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 <= 10⁵
0 <= rowCosts[r], colCosts[c] <= 10⁴
startPos.length == 2
homePos.length == 2
0 <= start_row, home_row < m
0 <= start_col, home_col < n

解法

方法一：贪心

我们不妨假设机器人的初始位置为 \((x_0, y_0)\)，家所在的位置为 \((x_1, y_1)\)。

如果 \(x_0 < x_1\)，那么机器人需要往下走，需要经过的行是 \([x_0 + 1, x_1]\)，总代价为 \(\sum_{i = x_0 + 1}^{x_1} rowCosts[i]\)；如果 \(x_0 > x_1\)，那么机器人需要往上走，需要经过的行是 \([x_1, x_0 - 1]\)，总代价为 \(\sum_{i = x_1}^{x_0 - 1} rowCosts[i]\)；如果 \(x_0 = x_1\)，那么机器人不需要往上下走，总代价为 \(0\)。

同理，如果 \(y_0 < y_1\)，那么机器人需要往右走，需要经过的列是 \([y_0 + 1, y_1]\)，总代价为 \(\sum_{j = y_0 + 1}^{y_1} colCosts[j]\)；如果 \(y_0 > y_1\)，那么机器人需要往左走，需要经过的列是 \([y_1, y_0 - 1]\)，总代价为 \(\sum_{j = y_1}^{y_0 - 1} colCosts[j]\)；如果 \(y_0 = y_1\)，那么机器人不需要往左右走，总代价为 \(0\)。

答案为上下走的总代价与左右走的总代价之和。

时间复杂度 \(O(m + n)\)，其中 \(m\) 和 \(n\) 分别是 \(rowCosts\) 和 \(colCosts\) 的长度。空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScriptRust

class Solution:
    def minCost(
        self,
        startPos: List[int],
        homePos: List[int],
        rowCosts: List[int],
        colCosts: List[int],
    ) -> int:
        x0, y0 = startPos
        x1, y1 = homePos
        dx = sum(rowCosts[x0 + 1 : x1 + 1]) if x0 < x1 else sum(rowCosts[x1:x0])
        dy = sum(colCosts[y0 + 1 : y1 + 1]) if y0 < y1 else sum(colCosts[y1:y0])
        return dx + dy

class Solution {
    public int minCost(int[] startPos, int[] homePos, int[] rowCosts, int[] colCosts) {
        int x0 = startPos[0], y0 = startPos[1];
        int x1 = homePos[0], y1 = homePos[1];
        int dx = x0 < x1 ? calc(rowCosts, x0 + 1, x1) : calc(rowCosts, x1, x0 - 1);
        int dy = y0 < y1 ? calc(colCosts, y0 + 1, y1) : calc(colCosts, y1, y0 - 1);
        return dx + dy;
    }

    private int calc(int[] nums, int i, int j) {
        int res = 0;
        for (int k = i; k <= j; ++k) {
            res += nums[k];
        }
        return res;
    }
}

class Solution {
public:
    int minCost(vector<int>& startPos, vector<int>& homePos, vector<int>& rowCosts, vector<int>& colCosts) {
        auto calc = [](vector<int>& nums, int i, int j) {
            int res = 0;
            for (int k = i; k <= j; ++k) {
                res += nums[k];
            }
            return res;
        };
        int x0 = startPos[0], y0 = startPos[1];
        int x1 = homePos[0], y1 = homePos[1];
        int dx = x0 < x1 ? calc(rowCosts, x0 + 1, x1) : calc(rowCosts, x1, x0 - 1);
        int dy = y0 < y1 ? calc(colCosts, y0 + 1, y1) : calc(colCosts, y1, y0 - 1);
        return dx + dy;
    }
};

func minCost(startPos []int, homePos []int, rowCosts []int, colCosts []int) int {
    x0, y0 := startPos[0], startPos[1]
    x1, y1 := homePos[0], homePos[1]
    calc := func(nums []int, i int, j int) int {
        res := 0
        for k := i; k <= j; k++ {
            res += nums[k]
        }
        return res
    }
    dx := 0
    if x0 < x1 {
        dx = calc(rowCosts, x0+1, x1)
    } else {
        dx = calc(rowCosts, x1, x0-1)
    }
    dy := 0
    if y0 < y1 {
        dy = calc(colCosts, y0+1, y1)
    } else {
        dy = calc(colCosts, y1, y0-1)
    }
    return dx + dy
}

function minCost(
    startPos: number[],
    homePos: number[],
    rowCosts: number[],
    colCosts: number[],
): number {
    const calc = (nums: number[], i: number, j: number): number => {
        let res = 0;
        for (let k = i; k <= j; ++k) {
            res += nums[k];
        }
        return res;
    };

    const [x0, y0] = startPos;
    const [x1, y1] = homePos;

    const dx = x0 < x1 ? calc(rowCosts, x0 + 1, x1) : calc(rowCosts, x1, x0 - 1);

    const dy = y0 < y1 ? calc(colCosts, y0 + 1, y1) : calc(colCosts, y1, y0 - 1);

    return dx + dy;
}

impl Solution {
    pub fn min_cost(
        start_pos: Vec<i32>,
        home_pos: Vec<i32>,
        row_costs: Vec<i32>,
        col_costs: Vec<i32>,
    ) -> i32 {
        let calc = |nums: &Vec<i32>, i: i32, j: i32| -> i32 {
            let mut res = 0;
            for k in i..=j {
                res += nums[k as usize];
            }
            res
        };

        let x0 = start_pos[0];
        let y0 = start_pos[1];
        let x1 = home_pos[0];
        let y1 = home_pos[1];

        let dx = if x0 < x1 {
            calc(&row_costs, x0 + 1, x1)
        } else {
            calc(&row_costs, x1, x0 - 1)
        };

        let dy = if y0 < y1 {
            calc(&col_costs, y0 + 1, y1)
        } else {
            calc(&col_costs, y1, y0 - 1)
        };

        dx + dy
    }
}

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

题目描述

解法

方法一：贪心

评论