Keyboarding

Naive: BFS for each character. 10,000*50^2 = 25,000,000....right???? NOT. greedy solution (arriving at each key as fast as possible) may not be optimal for getting to the NEXT character fastest due to fact that keys can be multiple space wide, and depending on how you get to it and its shape, you could skip several presses.

So we have to find the fastest way to get to every location on the key, and then combine moving forward? YES exactly....

First solution: gather shortest distance to all individual locations on a key (that are reachable...if a key is > 3x3, you can't get to the middle). For your BFS's use a priority queue instead of a regular queue which ensures that nodes are processed in the right order (means slower locations to a previous key don't enter the next BFS until we've expanded the front to far enough away). Terminate each BFS when we've reached every possible location of the next key. This SHOULD be fast enough....since it's just the same 10,000*50^2. It seems a bit harder than necessary to code though

Better Solutoin: just DP where your state is (x-coordinate, y-coordinate, number of letters typed already), and when you reach the next character to type in your walk, you increment number typed when you save that state. Terminate when number of charaters typed = length of the word (where "enter" is your last character).

This is very similar to Road Rally in that we have a multi-step BFS like thing, and we can't greedily go from step to step, so we have to just add it to our DP state.