Best Commute to Databricks HQ (Grid + Mode Constraints + Time/Cost Tie-break)

Problem: Best Commute to Databricks HQ You live in San Francisco and want to commute from source S to destination D with the minimum total time. You are given: A 2D grid grid representing city blocks: X is a roadblock (cannot enter) S is the source D is the destination digits 1..4 represent transportation modes: 1 = Walk, 2 = Bike, 3 = Car, 4 = Train cost[1..4]: dollars per block for each mode time[1..4]: minutes per block for each mode Movement rules You may move only up/down/left/right (no diagonals). You may not enter X. Each move must go to a neighboring cell with the same mode as your current mode cell. In other words, once you enter a mode region (e.g. 2), you can only traverse adjacent 2 cells. S and D are special: From S, you may enter any adjacent mode cell. You may enter D from any adjacent mode cell. Objective For each mode m in {1,2,3,4}: If there exists a path from S to D whose intermediate cells (excluding S and D) are all mode m, then the mode is feasible. Total time = time[m] * number_of_blocks_moved Total cost = cost[m] * number_of_blocks_moved Return: The mode id with the minimum total time. Break ties by minimum total cost, then by smaller mode id. If no mode can reach D, return -1. I/O format (ACM style) Read from stdin: Two integers R C R lines, each a length-C string over {X,S,D,1,2,3,4} One line with 4 integers: cost1 cost2 cost3 cost4 One line with 4 integers: time1 time2 time3 time4 Output one integer: the selected mode id (or -1). Constraints 1 <= R, C <= 200 R*C <= 40000 0 <= cost[i], time[i] <= 1e6 Example Input 6 5 33S2X 3112X 31122 3111D 33334 44444 0 1 3 2 3 2 1 1 Output 3