我想左移一个 n*n 数组（n是 偶数），像这样的图像 m 次：
我花了一天时间寻找解决方案，但找不到通用的解决方案。
你知道解决这个问题的算法吗？或者任何可以帮助我的指南？
例如（每个括号代表数组中的一个单元格）：
n= 2 and m =1
before shifting :
(1) (2)
(3) (4)
after shifting :
(2) (4)
(0) (3)
第二个例子：
n= 4 and m =2
before shifting :
(1) (2) (3) (4)
(5) (6) (7) (8)
(9) (10) (11) (12)
(13) (14) (15) (16)
after shifting :
(3) (4) (8) (12)
(7) (11) (10) (16)
(6) (0) (0) (15)
(5) (9) (13) (14)
基本上，您正在尝试将数字沿螺旋从中间移动到外边缘。螺旋是一条缠绕的线，所以在我看来，解决方案是将数组存储为一维数组，第零个元素代表螺旋的中间，第 N 个元素（其中 N = nxn）作为最后一个元素在螺旋之外（或者你可以从外面开始向内工作）。
然后你的问题变得微不足道，但你有一个新问题是：给定一个坐标对，我需要访问数组中的哪个元素？我已经考虑了很长时间（即至少 10 分钟），我能想到的最佳答案是创建一个二维查找数组。在 4 x 4 的情况下，它看起来像这样：
15 14 13 12
4 3 2 11
5 0 1 10
6 7 8 9
或者像这样：
0 1 2 3
11 12 13 4
10 15 14 5
9 8 7 6
如果您从外部开始工作，您可以很容易地以编程方式生成查找数组（伪代码）：
fill the lookup array with -1s
Set location to (0, 0)
Set direction to east
Set counter to 0
while (counter < array size)
set location to counter
increment counter
if next location in current direction is off the edge or is not -1
turn right (east => south, south => west, west => north, north => east)
move one square in current direction
这是一个提示。
您可以获得一个有趣的递归解决方案。把你的矩阵想象成一堆相互嵌套的矩阵（例如，对于一个 nxn 矩阵，它里面还有一个 (n-2)x(n-2) 矩阵，等等。一个例子是矩阵
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
有一个子矩阵
6 7
10 11
较大矩阵外环上的元素是螺旋的第一部分。一旦你处理了这些转移，你就不需要担心它们了。您可以将矩阵的下一个环视为一个新矩阵。内矩阵是原始矩阵的子问题。
所以你需要找到一个可以应用于原始矩阵的外部元素的解决方案，然后将相同类型的解决方案应用于内部矩阵，依此类推，直到到达中心。如果你仔细想想，这就是 n 是偶数的原因。每个子矩阵的大小为 n-2 或 (n-2)-2 等，直到达到 2x2 的子矩阵。
这个想法很简单。你移动外壳/外壳，然后移动下一个内部，依此类推，直到没有其他东西可以移动。
在连续班次之间，您将下一个内部信封/外壳的第一个字符复制到最后一个信封/外壳的最后一个（刚刚腾出）。这为您提供连续性，提供信封/外壳之间的数据流。
要将矩形信封移动 1 个位置，您可以首先计算其中有多少元素（1x1 中的 1 个，2x2 中的 4 个，3x3 中的 8 个，4x4 中的 12 个，等等正方形）。
然后您可以沿着信封从 0 到 length-2 运行坐标/位置，将其转换为 2d 数组中的常规坐标。这将为您提供复制的位置。现在，源的位置是沿着信封的下一个位置，您可以类似地将其转换为 2d 坐标。
我在 C 中的实现：
#include <stdio.h>
/*
(2w+2h-4)/0 1 .. w-2 w-1
+---------------+
2w+2h-5 | | w
. | | .
. | | .
. | | .
2w+h-2 | | w+h-3
+---------------+
2w+h-3 2w+h-4 .. w+h-1 w+h-2
*/
int EnvelopeLength(int w, int h)
{
if (w <= 0 || h <= 0)
return 0;
if (h == 1)
return w;
if (w == 1)
return h;
return 2 * (w + h) - 4;
}
#if 0 // this function is currently unused
int Coords2EnvelopePosition(int x, int y, int w, int h)
{
int pos = -1;
if (w <= 0 || h <= 0)
pos = -1;
else if (w == 1 && h == 1)
pos = 0;
else if (h == 1)
pos = x;
else if (w == 1)
pos = y;
else if (y == 0)
pos = x;
else if (x == w - 1)
pos = w + y - 1;
else if (y == h - 1)
pos = 2 * w + h - x - 3;
else if (x == 0)
pos = 2 * w + 2 * h - y - 4;
return pos;
}
#endif
void EnvelopePosition2Coords(int* px, int* py, int w, int h, int pos)
{
*py = *px = -1;
if (w <= 0 || h <= 0)
*py = *px = -1;
else if (w == 1 && h == 1)
*py = *px = 0;
else if (h == 1)
*px = pos, *py = 0;
else if (w == 1)
*px = 0, *py = pos;
else if (pos < w)
*px = pos, *py = 0;
else if (pos <= w + h - 2)
*px = w - 1, *py = pos - w + 1;
else if (pos <= 2 * w + h - 3)
*px = 2 * w + h - 3 - pos, *py = h - 1;
else if (pos <= 2 * w + 2 * h - 5)
*px = 0, *py = 2 * w + 2 * h - 4 - pos;
}
void SpiralShift(char* a, int w, int h)
{
int w0 = w;
while (w > 0 && h > 0)
{
int len = EnvelopeLength(w, h), pos;
int xto, yto, xfrom, yfrom;
for (pos = 0; pos < len - 1; pos++)
{
EnvelopePosition2Coords(&xto, &yto, w, h, pos);
EnvelopePosition2Coords(&xfrom, &yfrom, w, h, pos + 1);
a[yto * w0 + xto] = a[yfrom * w0 + xfrom];
}
EnvelopePosition2Coords(&xto, &yto, w, h, len - 1);
if (w > 2 && h > 2)
{
EnvelopePosition2Coords(&xfrom, &yfrom, w - 2, h - 2, 0);
a[yto * w0 + xto] = a[w0 + 1 + yfrom * w0 + xfrom];
w -= 2;
h -= 2;
a += w0 + 1;
}
else
{
a[yto * w0 + xto] = ' ';
break;
}
}
}
void PrintSpiral(const char*s, int w, int h)
{
int x, y;
puts("Spiral:");
for (y = 0; y < h; y++)
{
for (x = 0; x < w; x++)
printf("%c ", s[y * w + x]);
puts("");
}
puts("");
}
int main(void)
{
char spiral1x1[1 * 1] =
"a";
char spiral2x2[2 * 2] =
"wo"
"dr";
char spiral5x6[5 * 6] =
"This i"
"ing ss"
"lce.e "
"lnetna"
"arips ";
int i;
PrintSpiral(spiral1x1, 1, 1);
for (i = 0; i < 1 * 1; i++)
{
SpiralShift(spiral1x1, 1, 1);
PrintSpiral(spiral1x1, 1, 1);
}
PrintSpiral(spiral2x2, 2, 2);
for (i = 0; i < 2 * 2; i++)
{
SpiralShift(spiral2x2, 2, 2);
PrintSpiral(spiral2x2, 2, 2);
}
PrintSpiral(spiral5x6, 6, 5);
for (i = 0; i < 5 * 6; i++)
{
SpiralShift(spiral5x6, 6, 5);
PrintSpiral(spiral5x6, 6, 5);
}
return 0;
}
输出（ideone）：
Spiral:
a
Spiral:
Spiral:
w o
d r
Spiral:
o r
d
Spiral:
r d
Spiral:
d
Spiral:
Spiral:
T h i s i
i n g s s
l c e . e
l n e t n a
a r i p s
Spiral:
h i s i s
n g s e
i e . n a
l c n e t
l a r i p s
Spiral:
i s i s
g s e n a
n . t
i e c n e s
l l a r i p
Spiral:
s i s a
s e n t
g e s
n . e c n p
i l l a r i
Spiral:
i s a
s e n t e s
n p
g . e c i
n i l l a r
Spiral:
i s a s
e n t e n p
s c i
. e r
g n i l l a
Spiral:
s a s p
n t e n c i
e e r
s . a
g n i l l
Spiral:
a s p i
t e n c e r
n . a
e l
s g n i l
Spiral:
a s p i r
e n c e . a
t l
n l
e s g n i
Spiral:
s p i r a
n c e . l
e l
t i
n e s g n
Spiral:
s p i r a l
c e . l
n i
e n
t n e s g
Spiral:
p i r a l l
e . i
c n
n g
e t n e s
Spiral:
i r a l l i
. n
e g
c
n e t n e s
Spiral:
r a l l i n
g
.
e s
c n e t n e
Spiral:
a l l i n g
s
. e
e c n e t n
Spiral:
l l i n g
s
e
n
. e c n e t
Spiral:
l i n g s
e
n
t
. e c n e
Spiral:
i n g s e
n
t
e
. e c n
Spiral:
n g s e n
t
e
n
. e c
Spiral:
g s e n t
e
n
c
. e
Spiral:
s e n t e
n
c
e
.
Spiral:
s e n t e n
c
e
.
Spiral:
e n t e n c
e
.
Spiral:
n t e n c e
.
Spiral:
t e n c e .
Spiral:
e n c e .
Spiral:
n c e .
Spiral:
c e .
Spiral:
e .
Spiral:
.
Spiral:
#include <stdio.h>
#include <stdlib.h>
#define N 4
void initialize(int *pa){
int i;
for(i=1;i<= N * N;++i)
*pa++ = i;
}
void print(int a[N][N]){
int i,j;
for(i=0;i<N;++i){
for(j=0;j<N;++j)
printf("(%2d)", a[i][j]);
printf("\n");
}
printf("\n");
}
void spiralShiftLeft(int a[N][N], int n){
int **pa;
int i,x,y,c,size=N*N,step;
pa = (int**)calloc(size, sizeof(int*));
x=y=0;//x,y is location
//c is counter
//step is control
step = N;
c=0;
while(c<size){
int s;
--step;
for(s=0;s<step;++s)
pa[c++] = &a[y][x++];//up part
for(s=0;s<step;++s)
pa[c++] = &a[y++][x];//right part
for(s=0;s<step;++s)
pa[c++] = &a[y][x--];//bottom part
for(s=0;s<step;++s)
pa[c++] = &a[y--][x];//left part
++x;++y;//next step start position
--step;
}
//shift
for(i=0;i<size;++i){
int p=i+n;
*pa[i] = (p<size) ? *pa[p] : 0;
}
free(pa);
}
//demo
int main (void){
int org[N][N];
initialize((int*)org);
print(org);
spiralShiftLeft(org, 2);
print(org);
return 0;
}