leetcode 2087. Minimum Cost Homecoming of a Robot in a Grid

题目

解法

解法1:最短路径问题（TLE）

bellman ford

class Solution:def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:m,n = len(rowCosts),len(colCosts)dists = [[float('inf')] * n for _ in range(m)]dists[startPos[0]][startPos[1]] = 0dirs = [[0,1],[0,-1],[1,0],[-1,0]]q = collections.deque()q.append(startPos)while q:i,j = q.popleft()for d in dirs:x,y = i + d[0],j + d[1]if x < 0 or x >= m or y < 0 or y >= n:continueif d[0] == 0:cost = colCosts[y]else:cost = rowCosts[x]if dists[i][j] + cost < dists[x][y]:dists[x][y] = dists[i][j] + costq.append([x,y])return dists[homePos[0]][homePos[1]]

dijkstra

class Solution:def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:m,n = len(rowCosts),len(colCosts)dists = [[float('inf')] * n for _ in range(m)]dists[startPos[0]][startPos[1]] = 0dirs = [[0,1],[0,-1],[1,0],[-1,0]]nodes = [[0,startPos[0],startPos[1]]]while nodes:_,i,j = heapq.heappop(nodes)for d in dirs:x,y = i + d[0],j + d[1]if x < 0 or x >= m or y < 0 or y >= n:continueif d[0] == 0:cost = colCosts[y]else:cost = rowCosts[x]if dists[i][j] + cost < dists[x][y]:dists[x][y] = dists[i][j] + costheapq.heappush(nodes,(dists[x][y],x,y))return dists[homePos[0]][homePos[1]]

最短路径相关接发参考这里

解法2

分析：绝大多数人一上来应该想到的就是最短路径问题的解法（包括我！）。实际上这个题目用最短路径方法去解是超时的。问题关键在于

1. 这边形成的图并不是每个节点都有cost，而是相同行的节点以及相同列的节点cost都相同
2. 从起点到终点，这两个之间夹的行和列必须经过
3. 行和列的cost都为非负数，所以每一行或者列都只需经过一次，没有可能经过两次
   所以只需要按照起点到终点的顺序把行和列的cost求和即可。值得注意的一点是，起始位置的行和列并不一定比终止位置的行和列小

class Solution:def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:m,n = len(rowCosts),len(colCosts)ans = 0start_row,end_row = startPos[0],homePos[0]start_col,end_col = startPos[1],homePos[1]if start_row < end_row:for i in range(start_row+1,end_row+1):ans += rowCosts[i]else:for i in range(start_row-1,end_row-1,-1):ans += rowCosts[i]if start_col < end_col:for i in range(start_col+1,end_col+1):ans += colCosts[i]else:for i in range(start_col-1,end_col-1,-1):ans += colCosts[i]return ans

c++版本

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