Choose fastest transportation mode on city grid

You live in a city modeled as a 2D grid. Each cell is either:

• A transportation mode 1..4 where:
  • 1 = Walk , 2 = Bike , 3 = Car , 4 = Train
• S = source (start)
• D = destination
• X = roadblock (cannot enter)

You may move only up, down, left, right (no diagonals).

A trip must use exactly one transportation mode for the whole route:

• For a chosen mode m , you may step from a cell to a neighboring cell only if the neighbor is either S , D , or has value m .
• You cannot step onto X .

For each mode m, if there exists a valid path from S to D using mode m, its total travel time and cost are:

• time = (#blocks traversed) * timePerBlock[m]
• cost = (#blocks traversed) * costPerBlock[m]

Where #blocks traversed is the number of moves (edges) along the chosen path.

Return the mode number (1–4) that yields the minimum total time. If multiple modes tie on time, return the one with the minimum total cost. If still tied, any tied mode is acceptable.

Example

Grid (rows):

|3|3|S|2|X|
|3|1|1|2|X|
|3|1|1|2|2|
|3|1|1|1|D|
|3|3|3|3|4|
|4|4|4|4|4|

costPerBlock = [0, 1, 3, 2] (for modes 1..4 respectively)

timePerBlock = [3, 2, 1, 1]

Input/Output

• Input: grid , costPerBlock[4] , timePerBlock[4]
• Output: an integer in {1,2,3,4} indicating the selected mode.

Notes

• You may assume S and D each appear exactly once.
• If a mode cannot reach D from S , ignore it.
• (Optional if needed) If no mode can reach D , return -1 .