具有 Zig Zag 顺序的 2D 数组到 1D 数组算法

Question

我有一个 8x8 数组，想将其转换为具有 64 个字段的一维数组。 但在这个特殊的之字形顺序中：

我想要聪明的方法，但我没有任何线索。我有两种可能的理论，但它们并不聪明。有什么想法吗？

Answer 1

有一个包含 64 个条目的数组，用于按照锯齿形模式访问索引的顺序保存索引。您可能会使用它们作为某些缓冲区的偏移量。这是 JPEG 的东西吧？

int[] zigzag = {0, 1, 8, 16, 9, 2, ... etc};

Answer 2

你可以试试这个：开始时，你向右走一步，然后在唯一允许对角线的方向上进行对角线移动（一开始是西南方向），一直循环直到列[0 ]。向下移动 1 步（使用一个标志来检查您之前是否向右走了 1 步，并且只有在此标志之前为 true 时，您才能向下移动；您可以将此标志更改为 false，并将向下标志更改为 true）并再次沿唯一允许的方向（东北）走对角线，直到到达 row[0]。直到 AC[70] 为止都很好，因为没有向下移动。此时，将 right 和 down 的两个标志重置为 false 并重新启动该过程。

Answer 3

为了帮助任何谷歌搜索但找不到答案的人，这里有一个我想出的简单的 Perl 算法来解决这个问题。

sub getPos{
    my ($x,$y,$size)=@_;
    my $d = $x+$y;
    my $m = $d-$size;
    my $p = (($d%2)?$x:$y);
    my $dist = ($d*($d+1))/2;
    my $index = $dist + $p;
    if($d >= $size){
        $index -= ($m+1)**2;
    }
    return $index;
}

您可以这样使用它：

for(my $x = 0; $x < $size; $x++){
    for(my $y = 0; $y < $size; $y++){
        $OneArray[getPos($x, $y, $size)] = $TwoArray[$x][$y];
    }
}

其中 $OneArray 是您要将 $TwoArray 转换为的一维数组。