Я прочитал все вопросы о переполнении стека относительно вращающихся матриц
и ни один из них не затрагивает ничего, кроме перемещения или поворота на 90 или 180 градусов в направлении как отдельных слоев, так и целых матриц.
Я уже ответил на вопрос относительно его выполнения, но я ищу быстрые и / или «на месте» методы, предпочтительно, но любые методы
кроме того, что я дал, было бы неплохо увидеть, хотя бы для
образовательные цели. Мой пример на Perl 5, но, если ваши намерения ясны, почти любой язык должен быть приемлемым.
Матрица, использованная в моем примере, выглядит следующим образом
# 2D array @arr has 3 layers.
# @arr is
# 0 1 2 3 4 5
# a b c d e f
# 5 4 3 2 1 0
# 9 8 7 6 5 4
# f e d c b a
# 4 5 6 7 8 9
Цель-> Повернуть средний слой на 2 места по часовой стрелке, чтобы получить следующее ...
Обратите внимание, что верхний левый угол среднего слоя, 'b c', переместился на 2 позиции вправо, а '8 4' с средней левой стороны теперь там, где был 'b c'.
# Rotated @arr is
# 0 1 2 3 4 5
# a 8 4 b c f
# 5 e 3 2 d 0
# 9 d 7 6 e 4
# f c b 5 1 a
# 4 5 6 7 8 9
В настоящее время я делаю что-то вроде этого, что, правда, ужасно медленно. Особенно на многих больших массивах.
#!/usr/bin/env perl
use strict; use warnings;
# Coordinates are $arr[$row][$col]
my @arr;
$arr[0][0]='0'; $arr[0][1]='1'; $arr[0][2]='2'; $arr[0][3]='3'; $arr[0][4]='4'; $arr[0][5]='5';
$arr[1][0]='a'; $arr[1][1]='b'; $arr[1][2]='c'; $arr[1][3]='d'; $arr[1][4]='e'; $arr[1][5]='f';
$arr[2][0]='5'; $arr[2][1]='4'; $arr[2][2]='3'; $arr[2][3]='2'; $arr[2][4]='1'; $arr[2][5]='0';
$arr[3][0]='9'; $arr[3][1]='8'; $arr[3][2]='7'; $arr[3][3]='6'; $arr[3][4]='5'; $arr[3][5]='4';
$arr[4][0]='f'; $arr[4][1]='e'; $arr[4][2]='d'; $arr[4][3]='c'; $arr[4][4]='b'; $arr[4][5]='a';
$arr[5][0]='4'; $arr[5][1]='5'; $arr[5][2]='6'; $arr[5][3]='7'; $arr[5][4]='8'; $arr[5][5]='9';
# Print matrix
print_matrix(@arr);
# Extract layer 2
my $target_layer=2;
my $layer_two=extract_layer($target_layer,@arr);
# From the top left corner of the layer, it is as follows
# bcde15bcde84
print "\n$layer_two\n";
# Rotate layer 2 clockwise 2 places
$layer_two=rotate_layer_cl($layer_two,2);
# 84bcde15bcde
print "$layer_two\n\n";
# Replace layer 2 in the same way
@arr=replace_layer($target_layer,$layer_two,@arr);
# Print again
print_matrix(@arr);
### Sub functions ###
# Extract layer by walking around it's coordinates like so
# [1,1]-[1,4] Top(left->right)
# [2,4]-[4,4] Right(top->bottom)
# [4,3]-[4,1] Bottom(right->left)
# [3,1]-[2,1] Left(bottom->top)
sub extract_layer {
my ($layer_cnt,@matrix)=@_;
my $width=scalar(@matrix);
my $layer_width=$width-$layer_cnt;
# layer_cnt=2
# width=6
# layer_width=4
my $layer;
for my $col ( $layer_cnt-1..$layer_width ) {
$layer.=$matrix[$layer_cnt-1][$col];
}
for my $row ( $layer_cnt..$layer_width ) {
$layer.=$matrix[$row][$layer_width];
}
my $cnt=$layer_width-1;
while ( $cnt >= $layer_cnt-1 ) {
$layer.=$matrix[$layer_width][$cnt];
$cnt--;
}
$cnt=$layer_width-1;
while ( $cnt >= $layer_cnt ) {
$layer.=$matrix[$cnt][$layer_cnt-1];
$cnt--;
}
return $layer;
}
# Shift input to the right by $n places, wrapping around.
sub rotate_layer_cl {
my $n=$_[1];
my $buf=substr($_[0],length($_[0])-$n,$n);
return $buf.substr($_[0],0,length($_[0])-$n);
}
# Replace each char from the rotated layer.
sub replace_layer {
my ($layer_cnt,$layer,@matrix)=@_;
my $width=scalar(@matrix);
my $layer_width=$width-$layer_cnt;
# layer_cnt=2
# width=6
# layer_width=4
my $slot=0;
for my $col ( $layer_cnt-1..$layer_width ) {
$matrix[$layer_cnt-1][$col]=substr($layer,$slot,1);
$slot++;
}
for my $row ( $layer_cnt..$layer_width ) {
$matrix[$row][$layer_width]=substr($layer,$slot,1);
$slot++;
}
my $cnt=$layer_width-1;
while ( $cnt >= $layer_cnt-1 ) {
$matrix[$layer_width][$cnt]=substr($layer,$slot,1);
$slot++;
$cnt--;
}
$cnt=$layer_width-1;
while ( $cnt >= $layer_cnt ) {
$matrix[$cnt][$layer_cnt-1]=substr($layer,$slot,1);
$slot++;
$cnt--;
}
return @matrix;
}
# Prints given matrix
sub print_matrix {
foreach my $row (@_) {
my $cnt=0;
foreach my $char (@$row) {
print $char; $cnt++;
if ( $cnt == scalar(@_) ) {
print "\n";
} else {
print " ";
}
}
}
}
Вышеприведенный код выводит следующее,
0 1 2 3 4 5
a b c d e f
5 4 3 2 1 0
9 8 7 6 5 4
f e d c b a
4 5 6 7 8 9
bcde15bcde84
84bcde15bcde
0 1 2 3 4 5
a 8 4 b c f
5 e 3 2 d 0
9 d 7 6 e 4
f c b 5 1 a
4 5 6 7 8 9
, который показывает массив перед вращением среднего слоя, средний слой как строку, средний слой смещен как строку и окончательный результирующий массив после того, как средний слой был повернут на 2 места вправо.
----- EDIT -----
На данный момент самый быстрый способ, который я нашел, состоит в том, чтобы на самом деле не использовать полный 2D-массив, а поместить блок в обычный массив, например ...
my @hex_ary=('1234', '5678', '90ab', 'cdef');
Затем создайте строку слоя и сдвиньте ее так же, как показывает мой оригинальный пример.
Однако, поскольку они являются струнами, мне нужно только "ходить" вверх и вниз по сторонам. Верх и низ просто обозначены как ...
my $top=substr($hex_ary[0],0,3);
и
my $bot=reverse(substr($hex_ary[3],0,3));
для внешнего слоя в этом небольшом массиве 4x4, а стороны перебираются с помощью
my $right_side_char=substr($hex_ary[$top_row-$i],-1);
my $left_side_char=substr($hex_ary[$bot_row+$i],0,1);
Это увеличивает производительность ок. 100% от метода 2D, потому что количество срезов, взятых из массива, равно половине + 2.
Может быть, кто-то с лучшим пониманием C мог бы создать что-то более эффективное. Я чувствую, что Perl способен на такое только иногда.