Knight Move from Point A to Point B (Time Limit Exceeded)

[kaushik_acharya]

Problem: http://poj.org/problem?id=1915

My solution:
BFS traversal starting from point A till it visits point B.

I received Time Limit Exceeded for my solution. I am not able to figure out if there's another
more efficient solution. Hence asking for help here.

I have used C++ STL queue.
http://poj.org/showmessage?message_id=162038 (use google translate to convert from Chinese to English)
Here its mentioned that using list is faster than queue. But i wonder do I need to do such trick
to get my solution accepted.

[brianfry713]

I just wrote a simple solution using C++ STL queue and BFS and got AC in 110MS.
Using an array for a queue I got AC in 79MS.
Using C++ STL list I got TLE.

Post your code if you want.

[kaushik_acharya]

Thanks Brian.

I also got it using C++ STL queue. I think the mistake I did was precomputing possible moves from each square position.
This probably led to more time than assigned by online judge for some test cases in which the total no of steps from Point A to Point B were small.