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

Let's talk about algorithms!

Moderator: Board moderators

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)

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

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

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