Fastest SF Commute

A grid contains a start cell S, a destination cell D, and cells labeled 1, 2, 3, or 4 for four commute modes. A commute mode may move through S, D, and cells labeled with that mode's digit only. For each mode, find the shortest number of steps from S to D. The total time is steps * times[mode - 1], and the total cost is steps * costs[mode - 1]. Return [mode, totalTime, totalCost] for the mode with the smallest total time; break ties by smaller total cost. If no mode can reach the destination, return [-1, -1, -1].

Constraints

Movement is allowed in the four cardinal directions. The grid contains one S and one D.

Example 1

Input:

grid = ["S11","221","22D"]
times = [5,3,1,10]
costs = [1,3,1,1]

Output:

[2,12,12]

Explanation: Mode 1 and mode 2 each need four steps, but mode 2 has lower total time: 4 * 3 = 12.

Example 2

Input:

grid = ["S11","224","33D"]
times = [2,2,2,2]
costs = [1,1,1,1]

Output:

[-1,-1,-1]

Explanation: No commute mode has a connected path from start to destination.