Trick 4: how to get rid of TLE in BFS

Maybe I should change the trick to practice. Here the trick used is still early pruning.

1197. Minimum Knight Moves
If using naive BFS will get TLE for python.

1. We can improve it by changing x,y to absolute value since the moving pattern is symmetric. move to x,y will be the same as a move to abs(x), abs(y)
2. Prune the negative direction by using condition of r>-4 and c>-4, then no more TLE.

BFS by using list (1344ms)

BFS by using deque (1336ms)

BFS from both source and destination (460ms).

We can also use a DP solution. Which is very fast. Only 56 ms

Thanks for reading.

Reference

https://leetcode.com/problems/minimum-knight-moves/discuss/387120/Python3-Clear-short-and-easy-DP-solution-No-Need-for-BFS-or-math

https://leetcode.com/problems/minimum-knight-moves/discuss/386992/get-rid-of-TLE-for-python-BFS