A naive DFS solution is accepted here so that appears to be the purpose of this problem.

However it is easy to construct test cases where DFS would time out, and where efficient alternatives would be much more difficult to code.

Consider the following relatively small example, and let the search word be "oooooooAoooooooooooZoooooooooXooooooooooooYoooooo"

board:

ooooooooo
ooooAoooo
ooooooooo
ooooooooo
oXooooooo
oooooooYo
ooooooooo
ooooooooo
ooooooooo
ooooZoooo
ooooooooo

One can see that the correct answer is False by the following argument. There are 12 "o"s between "X" and "Y" in the search string. This is insufficient length to go around the "A" or the "Z", so any valid path must go between them. Likewise the only valid ways between "A" and "Z" must go through the middle. Hence these two paths must cross at some point. Because we are excluding diagonal hops from our definition of adjacency, there is no way for these paths to cross without at least one collision.

Scale up that example to a 200x200 grid and 1000-character word, where 99+% of the chars are "o". In such a case the number of paths DFS might need to explore could grow close to O(3^w) where w is the word length.

I suggest re-specifying the problem constraints to communicate some kind of lower bound on the entropy of the board (and maybe word), which would provide cover for DFS being an efficient solution. Presently we are told nothing about the statistics of character frequencies in the board and the word.