Knight's Shortest Path on Chessboard

Question

I've been practicing for an upcoming programming competition and I have stumbled across a question that I am just completely bewildered at. However, I feel as though it's a concept I should learn now rather than cross my fingers that it never comes up.

Basically, it deals with a knight piece on a chess board. You are given two inputs: starting location and ending location. The goal is to then calculate and print the shortest path that the knight can take to get to the target location.

I've never dealt with shortest-path-esque things, and I don't even know where to start. What logic do I employ to go about tackling this?

P.S. If it's of any relevance, they want you to supplement the knight's normal moves by also allowing it to move to the four corners of the square formed by the (potentially) eight moves a knight can make, given that the center of the square is the knight's location.

Answer 1

EDIT: See simon's answer, where he fixed the formula presented here.

Actually there is an O(1) formula

This is an image that I've made to visualize it ( Squares a knight can reach on N^th move are painted with same color ).

Can you notice the pattern here?

Although we can see the pattern, it is really hard to find the function f( x , y ) that returns the number of moves required to go from square ( 0 , 0 ) to square ( x , y )

But here is the formula that works when 0 <= y <= x

int f( int x , int y ) {     int delta = x - y;      if( y > delta )         return 2 * ( ( y - delta ) / 3 ) + delta;     else         return delta - 2 * ( ( delta - y ) / 4 ); } 

Note: This question was asked on SACO 2007 Day 1
And solutions are here