文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一個 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 <= 10^5 0 <= rowCosts[r], colCosts[c] <= 10^4 startPos.length == 2 homePos.length == 2 0 <= startrow, homerow < m 0 <= startcol, homecol < n

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-cost-homecoming-of-a-robot-in-a-grid
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 首先不管怎么走不能走到，起點和終點構成的矩形之外，會增加額外的花費
• 然后在上面條件下，不論怎么走，按照兩個方向的分量來看，花費都是一樣的：行的花費+列的花費

class Solution { public:int minCost(vector<int>& startPos, vector<int>& homePos, vector<int>& rowCosts, vector<int>& colCosts) {int ans = 0;if(homePos[0] >= startPos[0])for(int i = startPos[0]+1; i <= homePos[0]; ++i)ans += rowCosts[i];elsefor(int i = startPos[0]-1; i >= homePos[0]; --i)ans += rowCosts[i];if(homePos[1] >= startPos[1])for(int i = startPos[1]+1; i <= homePos[1]; ++i)ans += colCosts[i];elsefor(int i = startPos[1]-1; i >= homePos[1]; --i)ans += colCosts[i];return ans;} };

140 ms 146.3 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 2087. 网格图中机器人回家的最小代价（脑筋急转弯）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。