Grid BFS: choose best travel mode by shortest time then lowest cost

You are given a 2D character grid grid, where: 'S' is the start cell 'D' is the destination cell 'X' is a blocked cell '1'..'4' are road/type cells You may move one step at a time in 4 directions (up/down/left/right). There are 4 travel modes mode ∈ {1,2,3,4}: For a chosen mode, you may enter only cells equal to that mode (character '1'..'4') plus 'S' and 'D'. You may not enter 'X' or other mode cells. If the shortest path from S to D under this mode takes steps moves, then total time = steps * time_map[mode] and cost = steps * cost_map[mode]. Mappings (for mode 1..4): time_map = [3, 2, 1, 1] cost_map = [0, 1, 3, 2] Choose the best mode such that: Minimize total time; Break ties by minimizing total cost; Modes that cannot reach D from S are invalid. Return the best mode (an integer 1..4). If no mode can reach, return -1. Examples Example 1: S11 X21 11D Output: 1 Example 2: S2X 12X 11D Output: 2 Constraints (Not provided in the post; confirm with interviewer) 1 ≤ m, n ≤ 200 Exactly one S and one D exist in the grid Example Input 3 3 S11 X21 11D Output 1