FastPrep
Problem · Matrix

Minimize Commute

Learn this problem
● MediumDatabricks logoDatabricksFULLTIMEOA

Problem statement

You are given a city grid containing one S, one D, blocked cells X, and transport cells 1 through 4 for Walk, Bike, Car, and Train.

Choose exactly one transport mode. You may move one cell at a time in the four cardinal directions and may enter only S, D, and cells labeled with the chosen mode. Blocked cells and cells for other modes are impassable.

The arrays time and cost give per-block values in the order Walk, Bike, Car, Train. For every reachable mode, use its shortest path from S to D. Return the mode with minimum total time; break a total-time tie by minimum total cost.

Function

minimizeCommute(grid: String[][], time: int[], cost: int[]) → String

Examples

Example 1

grid = [["3","3","S","2","X","X"],["3","1","1","2","X","2"],["3","1","1","2","2","2"],["3","1","1","1","D","3"],["3","3","3","3","3","4"],["4","4","4","4","4","4"]]time = [3, 2, 1, 1]cost = [0, 1, 3, 2]return = "Bike"

Bike reaches D in five blocks for total time 5 × 2 = 10. Walk needs five blocks for time 15, Car needs eleven blocks for time 11, and Train is unreachable, so Bike is fastest.

Constraints

  • 1 ≤ rows, cols ≤ 100
  • Grid contains exactly one 'S' and one 'D'
  • time.length == cost.length == 4
  • At least one mode can reach 'D'

More Databricks problems

drafts saved locally
public String minimizeCommute(String[][] grid, int[] time, int[] cost) {
    // write your code here
}
grid[["3","3","S","2","X","X"],["3","1","1","2","X","2"],["3","1","1","2","2","2"],["3","1","1","1","D","3"],["3","3","3","3","3","4"],["4","4","4","4","4","4"]]
time[3, 2, 1, 1]
cost[0, 1, 3, 2]
expected"Bike"
checking account