You are given a 2D grid representing a city commute map. The grid contains exactly one start cell S and exactly one destination cell D.
Each other cell is one of:
-
1
,
2
,
3
, or
4
: a road usable only by that commute mode.
-
X
: blocked and cannot be used by any commute mode.
There are four commute modes, numbered 1 through 4. For each mode i, you are also given:
-
time[i]
: time required to move one step using mode
i
.
-
cost[i]
: cost required to move one step using mode
i
.
A commute mode may move up, down, left, or right. Mode i may move through cells labeled i, and may also enter S and D. It cannot move through cells labeled with other mode numbers or through blocked cells.
For each commute mode that can reach D from S, compute:
-
total time = number of steps in its shortest path multiplied by
time[i]
-
total cost = number of steps in its shortest path multiplied by
cost[i]
Return the commute mode that has the smallest total time. If multiple modes have the same total time, return the one with the smallest total cost. If there is still a tie, return the smallest mode number. If no commute mode can reach the destination, return -1.