<p>There is an <code>m x n</code> grid, where <code>(0, 0)</code> is the top-left cell and <code>(m - 1, n - 1)</code> is the bottom-right cell. You are given an integer array <code>startPos</code> where <code>startPos = [start<sub>row</sub>, start<sub>col</sub>]</code> indicates that <strong>initially</strong>, a <strong>robot</strong> is at the cell <code>(start<sub>row</sub>, start<sub>col</sub>)</code>. You are also given an integer array <code>homePos</code> where <code>homePos = [home<sub>row</sub>, home<sub>col</sub>]</code> indicates that its <strong>home</strong> is at the cell <code>(home<sub>row</sub>, home<sub>col</sub>)</code>.</p>

<p>The robot needs to go to its home. It can move one cell in four directions: <strong>left</strong>, <strong>right</strong>, <strong>up</strong>, or <strong>down</strong>, and it can not move outside the boundary. Every move incurs some cost. You are further given two <strong>0-indexed</strong> integer arrays: <code>rowCosts</code> of length <code>m</code> and <code>colCosts</code> of length <code>n</code>.</p>

<ul>
	<li>If the robot moves <strong>up</strong> or <strong>down</strong> into a cell whose <strong>row</strong> is <code>r</code>, then this move costs <code>rowCosts[r]</code>.</li>
	<li>If the robot moves <strong>left</strong> or <strong>right</strong> into a cell whose <strong>column</strong> is <code>c</code>, then this move costs <code>colCosts[c]</code>.</li>
</ul>

<p>Return <em>the <strong>minimum total cost</strong> for this robot to return home</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/10/11/eg-1.png" style="width: 282px; height: 217px;" />
<pre>
<strong>Input:</strong> startPos = [1, 0], homePos = [2, 3], rowCosts = [5, 4, 3], colCosts = [8, 2, 6, 7]
<strong>Output:</strong> 18
<strong>Explanation:</strong> One optimal path is that:
Starting from (1, 0)
-&gt; It goes down to (<u><strong>2</strong></u>, 0). This move costs rowCosts[2] = 3.
-&gt; It goes right to (2, <u><strong>1</strong></u>). This move costs colCosts[1] = 2.
-&gt; It goes right to (2, <u><strong>2</strong></u>). This move costs colCosts[2] = 6.
-&gt; It goes right to (2, <u><strong>3</strong></u>). This move costs colCosts[3] = 7.
The total cost is 3 + 2 + 6 + 7 = 18</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> startPos = [0, 0], homePos = [0, 0], rowCosts = [5], colCosts = [26]
<strong>Output:</strong> 0
<strong>Explanation:</strong> The robot is already at its home. Since no moves occur, the total cost is 0.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == rowCosts.length</code></li>
	<li><code>n == colCosts.length</code></li>
	<li><code>1 &lt;= m, n &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= rowCosts[r], colCosts[c] &lt;= 10<sup>4</sup></code></li>
	<li><code>startPos.length == 2</code></li>
	<li><code>homePos.length == 2</code></li>
	<li><code>0 &lt;= start<sub>row</sub>, home<sub>row</sub> &lt; m</code></li>
	<li><code>0 &lt;= start<sub>col</sub>, home<sub>col</sub> &lt; n</code></li>
</ul>

# 2024/09/12
# 面试前刷Goldman高频题目
#
# 典型的BFS-2问题
# 还是写一下
# 
import heapq
class Solution:
    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:
        if startPos == homePos:
            return 0

        n = len(rowCosts)
        m = len(colCosts)

        heap = []
        heapq.heappush(heap, (0, tuple(startPos)))
        visited = set()

        while heap:
            cost, node = heapq.heappop(heap)
            if node == tuple(homePos):
                return cost
            if node in visited:
                continue
            visited.add(node)

            for dx, dy in [1, 0], [-1, 0], [0, 1], [0, -1]:
                x = node[0] + dx
                y = node[1] + dy

                if 0 <= x < n and 0 <= y < m:
                    if x == node[0]:
                        heapq.heappush(heap, (cost + colCosts[y], (x, y)))
                    else:
                        heapq.heappush(heap, (cost + rowCosts[x], (x, y)))

        return -1
# 超时了，说明BFS-2不是最优解
# 感觉可以DP
# 不对，可恶，这题，直接count就行，因为：
# The solution relies on the observation that we must cross each row and each column between given positions to get from the startPos to the homePos. So, we will always incur cost of each row and column between home and start positions atleast once.
# It must also be observed that it's always best to travel through rows and column in the direction of start to end position and never beneficial to go in the opposite direction since we would then incur costs twice with no benefits. That is, we must traverse the shortest path from start to end.
class Solution:
    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:
        result, i, j = 0, startPos[0], startPos[1]
        while i != homePos[0]:
            i += 1 if i < homePos[0] else -1
            result += rowCosts[i]
        while j != homePos[1]:
            j += 1 if j < homePos[1] else -1
            result += colCosts[j]

        return result




1097