chess - 棋盘上骑士的最短路径

Question

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

基本上，它处理的是棋盘上的骑士棋子。您将获得两个输入:起始位置和结束位置。目标是计算并打印骑士到达目标位置所需的最短路径。

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

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

Answer 1

编辑: See simon's answer ，他修正了这里提出的公式。

其实有一个O(1)公式

这是我为了可视化它而制作的图像(骑士在第 N^th 步中可以到达的方 block 涂有相同的颜色)。

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

虽然我们可以看到模式，但是要找到函数 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 );
}

注意:此问题是在 SACO 2007 Day 1 上提出的
解决方案是 here