Find Optimal Commute

Problem Overview

You are commuting across a simplified map of San Francisco, represented as a 2D grid. Each cell on the grid is one of the following:

• 'S': Your home location (starting point)
• 'D': Your office location (destination)
• A digit from '1' to k: A street segment reserved for exactly one transportation mode
• 'X': An impassable roadblock You're also given three arrays with length k:
• modes: The name of each available transportation mode (e.g., ["bike", "bus", "walk", "scooter"])
• times: The time (in minutes) required to traverse a single block using each mode
• costs: The cost (in dollars) to traverse a single block using each mode

Movement Rules

• Movement is allowed up, down, left, and right only (no diagonal movement)
• You may only travel along contiguous cells of the same transportation mode (i.e., same digit)
• You cannot switch modes mid-journey in the base problem
• You cannot move between cells of different modes, nor can you cross roadblocks ('X') For each mode i (0-indexed), the time and cost to traverse a single block are given by times[i] and costs[i], respectively. [Source: darkinterview.com] The total travel time and total cost are calculated as the sum of the time and cost for each mode cell traversed along the path from 'S' to 'D'. Note that 'S' and 'D' are special cells (not mode cells) and do not contribute to the cost.

Objective

Return the name of the transportation mode that yields the minimum total time from 'S' to 'D'.

• If multiple modes result in the same minimum time, return the one with the lowest total cost
• Return an empty string "" if no valid route exists