计算骑士棋子所需的移动次数[关闭]

#1 楼

\ $ O（1）\ $讨论


是否可以计算\ $ O（1）\ $时间复杂度中的距离？


是的。

这个问题被称为“骑士距离”问题，通过谷歌搜索找到了许多参考文献。

这个问题是由于南非“计算机奥林匹克竞赛”于2007年为高中生解决....（我知道，这些天孩子们.... :)）。该规范使得程序的某些输入值足够大，使得\ $ O（n）\ $解决方案无法在所需的时间限制内进行计算，因此要获得（设计和）计算\所需的满分。 $ O（1）\ $系统。

问题说明以及\ $ O（1）\ $解决方案的足够说明。万一.za网络死了，这是解决方案的描述：


4 Ni的骑士

（x，y）坐标50％的约束很小，足以生成一个完整的网格，其中包含从任意点到（0,0）所需的最小移动次数。可以通过广度优先
搜索（BFS）生成网格。

我们知道到达（0,0）需要0步。因此，我们知道
点（1,2），（2,1）和其他六个运动每个都需要运动1
。从最短距离1的每个点中，我们可以
在每个方向上采取另一步骤以最短路径2。但是，
一些动作会使我们回到已经找到的点a
距离较短，因此我们放弃了这种移动。我们继续
直到网格填满，然后使用网格找到每个骑士的距离。

要获得100％的打印效率，需要在纸上进行很多涂鸦进行一些关键的观察并制定一些公式。首先要注意的是
，网格沿x，y轴和线y = ±x是对称的。
因此，您可以将所有点(x, y)转换为等效点
，以便新的0 ≤ y ≤ x。

神奇的公式是：

$$
f（ x，y）= \ left \ {
\ begin {array} {ll}
2 \ left \ lfloor \ frac {y-\ delta} {3} \ right \ rfloor + \ delta＆\ mbox {if} y> \ delta \\
\ delta-2 \ left \ lfloor \ frac {\ delta-y} {4} \ right \ rfloor和\ mbox {otherwise}
\ end {数组}
\右。
$$

其中\ $δ= x − y \ $。


是否存在错误

是的。...骑士可以进入所有广场。为什么会有限制？

我将您的代码放入一个Ideone中，该Ideone循环遍历位置（0,0）到（9,9）的100个目标...，结果是令人失望...您的代码是否有效？

否。它不是。它产生非常错误的值.....

现在，我上面引用的算法似乎也没有产生好的值（至少是短距离....），但是认真吗？您的代码几乎不起作用:(

很多，很多-1距离，很多0 ......

#2 楼

一些注意事项（如您所说，除了效率）：



您定义的ABS带有圆括号，这不是C程序员声明宏的常规方法，因此它们不是'也有问题。

#define ABS(a) do { typeof (a) _a = (a); _a > 0 ? _a : -_a; } while(0)

在这种情况下，也没有必要使用typeof。只需使用abs()中的<math.h>函数，或定义一个更简单的ABS宏即可。

#define ABS(x) ((x) > 0 ? x : -x)

请注意，必须使用fabs()来查找浮点的绝对值使用<math.h>库输入数字。

为什么所有的单个字母变量名称都大写？

您需要让一些代码喘口气以使其更易于阅读（在我看来）。

X += distX > 0 ? 2 : -2;

使用更多注释来说明您的代码做什么以及为什么。不过请不要过度使用。

if (!(((A-X) % 2) ^ ((Y-B) % 2)))  //<insert description here>

#3 楼

我对此有一点建议：

#define ABS(a) ({ typeof (a) _a = (a); _a > 0 ? _a : -_a; })

首先，typeof是gcc扩展，因此通过使用它，您使代码的可移植性降低了。公平的说，对于像这样的小事情来说，这不是一个大问题，但要养成一个坏习惯。在这种情况下，甚至也不需要它。

#define ABS(x) ((x) > 0 ? x : -x)

也可以正常工作。 。 <math.h>为您定义abs（用于整数）和fabs（用于浮点值）。除非有很好的理由，否则请使用标准库。