410186: GYM103969 F Seeking Starburst

You just saw an ad on TV about Starburst and the new "juicy" version. Since you want to try it out, you want to go to the nearest convenience store to pick it up. When thinking about your options, you find three different transportation methods available to you. When evaluating these three options, you know you want to get there as fast as possible. If there are two different transportation methods that take the same amount of time, you will choose the one that saves money (you can use the saved money to buy more Starburst!). The three options are:

Bus (B): 3 minutes per unit of distance, 2 dollars per unit of distance

Car (C): 10 minutes per unit of distance, 10 dollars per unit of distance

Walk (W): 10 minutes per unit of distance, 5 dollars per unit of distance

Output the mode of transportation (B, C, or W) that is most optimal. If there is no path, return "None".

The first line contains two integers $$$m$$$ and $$$n$$$ ($$$1 \leq m, n \leq 750$$$), representing the number of rows and columns respectively. The next $$$m$$$ lines contain $$$n$$$ letters each. There is exactly one S and one E, representing the start and end, respectively. All other letters are B, C, or W, representing the mode of transportation available for that cell.

You may travel horizontally or vertically.

Output the mode of transportation (B, C, or W) that is most optimal. If there is no path from the start to the end that only uses a single mode of transportation, print "None".

4 4
BBCC
BSCC
BWWE
BBBB

B