Consider a test case like this:
AAAEZZZZZZZZZZZZZZZZZZZZZZ
ABCDEFGHIJKLMNOPQRSTUVWXYZ
AAAZZZZZZZZZZZZZZZZZZZZZZZ
When you find those As and the adjacent B, how many times are you going to search the same path from B to the final Z? How many times do you need to search that same path starting from B?
Memoisation is the answer.
(As an aside, the code would be less repetitive and error prone if you stored the offsets for each direction in a couple of arrays.)
