Problem Brief

Minimize Commute

FULLTIMEOA

You are given a 2D city grid and want to minimize your commute time from 'S' (start) to 'D' (destination).

Each cell in the grid is one of:

'S' — start (accessible by all modes)
'D' — destination (accessible by all modes)
'X' — blocked cell (impassable)
'1' — walkway (Walk only)
'2' — bike lane (Bike only)
'3' — car road (Car only)
'4' — train track (Train only)

You are also given a time array and a cost array, each of length 4, indexed as [Walk, Bike, Car, Train]. time[i] is the minutes per block for mode i, and cost[i] is the dollars per block.

You may only move horizontally or vertically (no diagonals). For each transportation mode, perform a BFS using only its matching cell type (plus 'S' and 'D') to find the shortest path. The total time for a mode is path_length × time[i]; total cost is path_length × cost[i].

Return the name of the mode (Walk, Bike, Car, or Train) with the minimum total time. If multiple modes tie on time, return the one with the minimum total cost.

1Example 1

Input

grid = [["S","2","2","D"]], time = [3, 2, 1, 1], cost = [0, 1, 3, 2]

Output

Bike

Explanation

Only Bike can traverse the '2' cells. Path: S→2→2→D (3 moves). Time = 3×2 = 6 min. No other mode has a valid path.

2Example 2

Input

grid = [["S","3","D"]], time = [3, 2, 1, 1], cost = [0, 1, 3, 2]

Output

Car

Explanation

Only Car can traverse the '3' cell. Path: S→3→D (2 moves). Time = 2×1 = 2 min.

3Example 3

Input

grid = [["S","1","1","D"]], time = [3, 2, 1, 1], cost = [0, 1, 3, 2]

Output

Walk

Explanation

Only Walk can traverse '1' cells. Path: S→1→1→D (3 moves). Time = 3×3 = 9 min.

4Example 4

Input

grid = [["S","D"]], time = [3, 2, 1, 1], cost = [0, 1, 3, 2]

Output

Train

Explanation

S and D are adjacent; all modes can travel directly from S to D (1 move). Times: Walk=3, Bike=2, Car=1, Train=1. Car and Train tie — Train costs less (2 < 3), so Train wins.

Constraints

Limits and guarantees your solution can rely on.

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