If you use a simple depth first search, your run time will depend on the order in which you examine the possible moves.

For example, always examining the moves in this order yields a TLE: (1,2), (1,-2), (-1,2), (-1,-2), (2,1), (2,-1), (-2,1), (-2,-1).

To get the fastest solutions you'll want to adapt the search order at each node in the search tree, but you can get an AC  with a static search order.