棋盘上骑士的最短路径

我一直在为即将到来的编程比赛进行练习，我偶然发现了一个我完全困惑的问题。然而，我觉得这是一个我现在应该学习的概念，而不是祈祷它永远不会出现。

基本上，它涉及棋盘上的骑士棋子。您将获得两个输入：起始位置和结束位置。目标是计算并打印骑士到达目标位置可以采取的最短路径。

我从来没有处理过最短路径式的事情，我什至不知道从哪里开始。我采用什么逻辑来解决这个问题？

附：如果有任何相关性，他们希望您通过允许骑士移动到由骑士可以进行的（可能）八个动作形成的正方形的四个角来补充骑士的正常动作，假设正方形的中心是骑士的位置。

EDIT: 参见西蒙的回答 https://stackoverflow.com/a/41704071/620438，他修正了这里提出的公式。

其实有一个O(1)的公式

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 ).

你能注意到这里的模式吗？

虽然我们可以看到图案，但是要找到功能确实很难f( x , y )返回从方格开始所需的移动次数( 0 , 0 )到平方( x , y )

但这是适用于以下情况的公式：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 );
}

注意：这个问题是在2007 年 SACO 第一天 http://olympiad.cs.uct.ac.za/old/saco2007/day1_2007.pdf
解决方案是here http://olympiad.cs.uct.ac.za/old/saco2007/day1_2007_solutions.pdf