Page 1 of 1

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

Posted: Wed Jul 17, 2013 2:21 pm
by 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.

Re: Knight Move from Point A to Point B (Time Limit Exceeded

Posted: Wed Jul 17, 2013 10:45 pm
by 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.

Re: Knight Move from Point A to Point B (Time Limit Exceeded

Posted: Sat Jul 20, 2013 8:43 pm
by 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.