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

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
kaushik_acharya
New poster
Posts: 17
Joined: Thu Jul 28, 2005 3:05 pm
Location: Bangalore, India

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

Post by kaushik_acharya » Wed Jul 17, 2013 2:21 pm

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.
My experience with Fraudster khari

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

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

Post by brianfry713 » Wed Jul 17, 2013 10:45 pm

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.
Check input and AC output for thousands of problems on uDebug!

kaushik_acharya
New poster
Posts: 17
Joined: Thu Jul 28, 2005 3:05 pm
Location: Bangalore, India

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

Post by kaushik_acharya » Sat Jul 20, 2013 8:43 pm

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.
My experience with Fraudster khari

Post Reply

Return to “Algorithms”