3

(0,0,0) から (100,100,100) までの 3D (整数) 座標のセットがあるとします。各座標に複数回アクセスすることなく、可能な各座標 (100^3 の可能な座標) にアクセスしたいとします。

隣接するステップの各座標間の差の合計は 2 を超えることはできません (これが可能かどうかはわかりません。可能でない場合は最小化されます)。たとえば、(0,2,1) から (2, |x1-x2|+|y1-y2|+|z1-z2| であるため、合計差は 5 です。= 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

4

3 に答える 3

4

トリックの 1 つ (他のアプローチもあります) は、一度に 1 つの線 [セグメント]、一度に 1 つの平面 [正方形] を行うことです。質問の最後の部分に対処すると、訪問したボリュームのサイズが各次元で同じでなくても (例: 100 x 6 x 33 ブロック)、このアプローチは機能します。

言い換えると：

(0,0,0) から開始し、
セグメントの最後まで Z 軸上でのみ移動します。つまり、
(0,0,1), (0,0,2), (0,0,3), ... (0,0,100),
次に、次の行に移動します。
(0,1,100)
そして、ライン上で後ろに来る、すなわち
(0,1,99)、(0,1,98)、(0,1,97)、... (0,1,0)、
次の行の次、「進む」

そして、「パネルがペイントされる」まで繰り返します。
... (0,100,99), (0,100,100),
次に、最後に X 軸上で 1 だけ移動します。つまり、
(1,100,100)
 他のパネルで繰り返しますが、このパネルでは「上向き」になります
等

基本的に、各移動は 1 つの次元で、正確に 1 つずつ行われます。これは、101 x 101 x 101 の建物で部屋から部屋へと「歩いて」いるようなもので、各部屋は特定の軸上で直接隣の部屋につながることができます (つまり、斜めに結合することはありません)。

この種のロジックをプログラミング言語で実装するのは簡単です! やや難しい部分は、「行ったり来たり」に対処することだけです。つまり、特定の次元の変化の一部が正の場合もあれば、負の場合もあるという事実です)。

編集：（同じことを斜めに行うことについてのシドの質問）：
はい！問題は、[マンハッタン] の距離を 2 にすることができると述べているため、それはかなり可能です。これは、斜めに進むために必要なものです。
パスは上記のものと似ています。つまり、線を行ったり来たり (ここでは可変長の線のみ)、3 次元の次の「パネル」に移動し、「上向き」にのみ繰り返します。 」など

(0,0,0) (0,0,1)
(0,1,0) 最初の対角線、長さは 1 のみ。
(0,2,0)「振り向く」
(0,1,1) (0,0,2) 2 番目の対角線: 長さ 2
(0,0,3)「振り向く」
(0,1,2) (0,2,1) (0,3,0) 3 番目の対角線: 長さ 3
(0,4,0) 振り向く
等

これらのアプローチを組み合わせて使用​​することは、完全な「パネル」のレベル (たとえば斜めに開始し、次のパネルを水平に行うなど) と、特定のパネル内 (たとえば斜めに開始するなど) の両方で可能ですが、一番上の行は、水平パターンに進み、「左側」側でループするときに少し早く停止します。これは、その側の一部が対角線で処理されているためです。
事実上、これにより、スペース全体を「ペイント」するかなり多くの (しかし明らかに有限の) 方法が可能になります。重要なことは、(あまりにも多くの) 塗装されていない隣接エリアを後に残すことを避けることです。

于 2009-11-22T07:00:03.177 に答える
0

問題の特殊なケースを解決するように思われるGray Codesを一般化できるかもしれません。

于 2009-11-22T06:52:54.643 に答える
0

最初は些細なことのように思えますが、始めるとトリッキーです! 特にステップは 1 または 2です。
これは答えではなく、特定のシーケンスの最初の 10 以上のステップのデモンストレーションであり、他の人が視覚化するのに役立つことを願っています。シドさん、次の文章が間違っていたら教えてください:

s = 前の座標からのステップ数
c1 = 条件 1 (x = y = z)
c2 = 条件 2 (x!= y!= z)
(x,y,z) s c1 c2
---------------
(0,0,0) * (開始)
(0,0,1) 1
(0,1,0) 2
(1,0,0) 2
(1,0,1) 1
(1,1,0) 2
(1,1,1) 1 *
(2,1,1) 1
(2,0,1) 1 *
(2,0,0) 1
(2,1,0) 1 *
(2,2,0) 1
(2,2,1) 1
(2,2,2) 1 *
(2,3,2) 1
(2,3,3) 1
(3,3,3) 1 *
(3,3,1) 2
(3,2,1) 1 *
(3,2,0) 1 *
  .
  .
  .
于 2009-11-22T06:59:24.347 に答える