Алгоритм двухмерного массива в одномерный массив с зигзагообразным порядком

Question

Я получил массив 8x8 и хочу преобразовать его в одномерный массив с 64 полями. Но в этом особом зигзагообразном порядке:

Я хочу умный способ, но у меня нет подсказки. У меня есть две возможные теории, но они не умны. Есть идеи?

Answer 1

Иметь массив с 64 записями, который содержит индексы в том порядке, в котором зигзагообразный шаблон будет их посещать. Вы вероятно использовали бы их как смещения от некоторого буфера. Это для JPEG, верно?

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

Answer 2

Вы можете попробовать это: когда вы начинаете, вы делаете 1 шаг вправо, а затем делаете диагональное движение в единственном направлении, которое разрешает диагонали (сначала это юго-запад), и зацикливаетесь до колонка [0]. Вы перемещаетесь на 1 шаг вниз (используйте флаг, чтобы проверить, сделали ли вы ранее 1 шаг вправо, и вы можете двигаться вниз только в том случае, если раньше этот флаг был истинным; вы можете изменить этот флаг на false и изменить флаг вниз на true) и снова возьмите диагональ в единственном разрешенном направлении (северо-восток), пока не достигнете строки [0]. Это будет хорошо до AC [70], так как нет движения вниз. На этом этапе сбросьте оба флажка для правого и обратного на ложное и перезапустите процесс.

Answer 3

Для помощи любому, кто ищет в Google и не может найти ответ, вот простой алгоритм 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 в.