graph - 无需重新访问即可遍历 3D 坐标的算法

Question

假设我们有一组从 (0,0,0) 到 (100,100,100) 的 3D(整数)坐标 我们希望访问每个可能的坐标(要访问的 100^3 个可能的坐标)而不访问每个坐标超过一次。

相邻步骤中每个坐标的差之和不能大于2(不知道可不可以，如果不行，那就最小化) 例如，从 (0,2,1) 到 (2,0,0) 的总差为 5，因为 |x1-x2|+|y1-y2|+|z1-z2| = 5

我们如何生成这样的坐标序列？

例如，开始: (0,0,0) (0,0,1) (0,1,0) (1,0,0) (1,0,1) (0,0,2) (0,1,1) (0,2,0) (1,1,0) (2,0,0) (3,0,0) (2,0,1) (1,0,2) (0,0,3) 等等……

任何人都知道一种算法会生成这样一个序列到任意坐标 (x,y,z)，其中 x=y=z 或者可以证明这样的算法不可能存在？谢谢

额外功劳:展示如何使用 x!=y!=z :D 生成这样的序列

Answer 1

技巧之一(还有其他方法)是一次一条线[线段]，一次一个平面[正方形]。对于问题的最后一部分，这种方法有效，即使访问的体积大小在每个维度上都不相同(例如:100 x 6 x 33 block )。

换句话说:

Start at (0,0,0), 
move only on the Z axis till the end of the segment, i.e.
(0,0,1), (0,0,2), (0,0,3), ... (0,0,100), 
Then move to the next line, i.e.
(0,1,100)
and come backward on the line, i.e.
(0,1,99), (0,1,98), (0,1,97), ... (0,1,0), 
Next to the next line, going "forward"

And repeat till the whole "panel is painted", i.e ending at
... (0,100,99), (0,100,100),
Then move, finally, by 1, on the X axis, i.e.
(1,100,100)
 and repeat on the other panel,but on this panel going "upward"
etc. 

本质上，每一步都是在一个维度上完成的，正好是一个维度。这有点像您在一个 101 x 101 x 101 的建筑物中从一个房间“走”到另一个房间，其中每个房间都可以通向给定轴上紧邻它的任何房间(即不对角连接)。

用编程语言实现这种逻辑是微不足道的!唯一具有一定挑战性的部分是处理“来回”，即有时给定维度的某些变化是积极的，有时是消极的。

编辑:(Sid 关于对角线做同样的问题):
是的!这是很有可能的，因为问题表明我们可以有一个 [Manhattan] 距离为 2，这是沿对角线移动所需要的。
该路径类似于上面列出的路径，即来回做线(这里只有可变长度的线)，然后移动到下一个“面板”，在三维空间中，重复，只“向上” "等

(0,0,0) (0,0,1)
(0,1,0)                  first diagonal, only 1 in lengh.
(0,2,0)                  "turn around"
(0,1,1) (0,0,2)          second diagonal: 2 in length
(0,0,3)                  "turn around"
(0,1,2) (0,2,1) (0,3,0)  third diagonal: 3 in length
(0,4,0)                  turn around
etc.

确实可以混合搭配这些方法，既可以在完整的“面板”级别上进行，例如对角线进行一个，水平进行下一个，也可以在给定的面板内进行，例如对角线开始，但是当在顶行时，继续水平模式，在“左侧”循环时简单地提前停止一点，因为该侧的一部分已经用对角线处理了。
实际上，这允许相当多(但显然是有限的)方法来“绘制”整个空间。关键是要避免留下(太多)未绘制(paint)的相邻区域，因为回到它们可能会把我们带到死胡同，或者可能需要“跳跃”超过 2 次。