Problem Brief

Fastest SF Commute

FULLTIMEPHONE SCREEN

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].

1Example 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.

2Example 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.

Constraints

Limits and guarantees your solution can rely on.

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