Show problems as
Classic problem #2087MediumArrayGreedy

Minimum Cost Homecoming of a Robot in a Grid

Real-world version: Toll to Drive the Rover Home
Tracked in this browser only
Read Minimum Cost Homecoming of a Robot in a Grid on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A rover sits on a grid of m rows by n columns at startPos = [startRow, startCol] and must reach homePos = [homeRow, homeCol].

One move takes the rover to a cell sharing an edge with the one it is on, and the grid may not be left. Moving into the cell at row r, column c costs rowCosts[r] when the move changed the row, and colCosts[c] when the move changed the column. Leaving a cell costs nothing, and the starting cell costs nothing.

Return the least total cost of driving the rover home.

Examples

Example 1

Input
startPos = [1, 0], homePos = [2, 3], rowCosts = [5, 4, 3], colCosts = [8, 2, 6, 7]
Output
18

The rover enters row 2 and columns 1, 2 and 3, costing 3 + 2 + 6 + 7 = 18.

Example 2

Input
startPos = [1, 1], homePos = [1, 1], rowCosts = [3, 4], colCosts = [5, 6]
Output
0

The rover is already home, so it enters no new row or column and pays nothing.

Example 3

Input
startPos = [2, 2], homePos = [0, 0], rowCosts = [1, 2, 3], colCosts = [4, 5, 6]
Output
12

Driving up and to the left, the rover enters rows 1 and 0 and columns 1 and 0, costing 2 + 1 + 5 + 4 = 12.

Constraints

  • 1 <= rowCosts.length <= 10^5
  • 1 <= colCosts.length <= 10^5
  • 0 <= rowCosts[r] <= 10^4
  • 0 <= colCosts[c] <= 10^4
  • startPos.length == 2
  • homePos.length == 2
  • 0 <= startPos[0] <= 99999
  • 0 <= startPos[1] <= 99999
  • 0 <= homePos[0] <= 99999
  • 0 <= homePos[1] <= 99999
  • Both positions lie inside the grid

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def rover_toll(startPos: list[int], homePos: list[int], rowCosts: list[int], colCosts: list[int]) -> int:
Java
public int roverToll(int[] startPos, int[] homePos, int[] rowCosts, int[] colCosts)

More on the same topics