考え方は単純です。外側のエンベロープ/シェルをシフトしてから、次の内側をシフトするというように、他にシフトするものがなくなるまで続けます。
連続するシフトの間に、次の内側のエンベロープ/シェルの最初の文字を、最後のエンベロープ/シェルの最後 (空になったばかり) にコピーします。これにより、連続性が得られ、エンベロープ/シェル間のデータ フローが提供されます。
長方形のエンベロープを 1 位置ずらすには、最初に要素の数を数えます (正方形の場合、1x1 に 1、2x2 に 4、3x3 に 8、4x4 に 12 など)。
次に、エンベロープに沿って 0 から長さ 2 までの座標/位置を実行し、それを 2 次元配列内の通常の座標に変換できます。これにより、コピーする位置が得られます。これで、ソースの位置はエンベロープに沿った次の位置になり、同様に 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:
