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

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

/*
 * 思路：
 * 1. 使用Java Stream计算行和列移动的代价。
 * 2. 使用IntStream遍历并计算每一步的代价。
 */

import java.util.stream.IntStream;

public class MinCostToHomeStream {
    public int minCost(int[] startPos, int[] homePos, int[] rowCosts, int[] colCosts) {
        int startRow = startPos[0];
        int startCol = startPos[1];
        int homeRow = homePos[0];
        int homeCol = homePos[1];

        // 计算行移动代价
        int rowCost = startRow < homeRow ?
            IntStream.rangeClosed(startRow + 1, homeRow).map(i -> rowCosts[i]).sum() :
            IntStream.rangeClosed(homeRow, startRow - 1).map(i -> rowCosts[startRow - (i - homeRow) - 1]).sum();

        // 计算列移动代价
        int colCost = startCol < homeCol ?
            IntStream.rangeClosed(startCol + 1, homeCol).map(i -> colCosts[i]).sum() :
            IntStream.rangeClosed(homeCol, startCol - 1).map(i -> colCosts[startCol - (i - homeCol) - 1]).sum();

        return rowCost + colCost;
    }
}

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

O(m + n)

O(1)