左移位阵列像链阵列
2023-09-11 04:14:33
作者：情话入心
我要向左移位的N * N个阵列（ N 的是偶数的），m次这样的图片：
我花了一天的时间找到一个解决办法，但我无法找到一个通用的解决方案。
你知道一个算法来解决这个问题呢？或者有什么指南，能帮助我吗？
例如（每个括号重新presents在阵列中的单元格）：
N = 2和M = 1
然后改成：
（1）（2）
（3）（4）
后移：
（2）（4）
（0）（3）
第二个例子：
N = 4和M = 2
然后改成：
（1）（2）（3）（4）
（5）（6）（7）（8）
（9）（10）（11）（12）
（13）（14）（15）（16）
后移：
（3）（4）（8）（12）
（7）（11）（10）（16）
（6）（0）（0）（15）
（5）（9）（13）（14）
解决方案
我们的想法很简单。你却将外封套/壳，然后转向下一个内，依此类推，直到没有什么别的转移。
连续轮班之间，你下副本内包/壳到最后信封/壳的最后一个（刚刚腾空）的第一个字符。这给你的连续性，提供信封/外壳之间的数据流。
要1个职位转移长方形的信封，你可以先算多少元素在里面（的4×4 2×2 1×1，4，8在3×3，12等的正方形）。
然后就可以从0沿信封坐标/位置，长度2，将其转换成普通坐标的二维数组中。这会给你的位置在哪里复制。现在，对于源的位置是非常下一个沿信封，你可以把它转换成2D同样的坐标。
我的C语言实现：
的#include＆LT; stdio.h中＆GT;
/ *
（2瓦特+ 2H-4）/ 0 1 ..瓦特-2-瓦特-1-
+ -------- +
2瓦特+ 2H-5 | | W¯¯
。 | | 。
。 | | 。
。 | | 。
2瓦特+ H-2 | | W + H-3
+ -------- +
2瓦特+ H-32瓦特+ H-4 .. W + H-1 W + H-2
* /
INT EnvelopeLength（INT W，INT高）
{
如果（瓦特＆所述; = 0 || H＆所述; = 0）
返回0;
如果（H == 1）
返回瓦;
如果（瓦特== 1）
返回H;
返回2 *（W + H） - 4;
}
＃如果0 //此功能目前未使用
INT Coords2EnvelopePosition（INT X，INT Y，INT W，INT高）
{
INT POS = -1;
如果（瓦特＆所述; = 0 || H＆所述; = 0）
POS = -1;
否则，如果（瓦特== 1＆安培;＆安培; H == 1）
POS = 0;
否则如果（H == 1）
POS = X;
否则，如果（瓦特== 1）
POS = Y;
否则，如果（Y == 0）
POS = X;
否则，如果（X = W - 1）
POS = W + Y - 1;
否则，如果（Y == ^ h - 1）
POS = 2 *宽+高 - X - 3;
否则，如果（X == 0）
POS = 2 * W + 2 * H - Y - 4;
返回POS机;
}
#ENDIF
无效EnvelopePosition2Coords（INT * PX，为int * PY，INT W，INT小时，INT POS）
{
*的py = *像素= -1;
如果（瓦特＆所述; = 0 || H＆所述; = 0）
*的py = *像素= -1;
否则，如果（瓦特== 1＆安培;＆安培; H == 1）
*的py = *像素= 0;
否则如果（H == 1）
* PX = POS，* PY = 0;
否则，如果（瓦特== 1）
*像素= 0，* PY = POS;
否则，如果（POS＆LT; W）
* PX = POS，* PY = 0;
否则，如果（POS＆LT; = W + H - 2）
* PX = W - 1，* PY = POS - W + 1;
否则，如果（POS＆LT; = 2 *宽+高 - 3）
* PX = 2 *宽+高 - 3 - POS，* PY = H - 1;
否则，如果（POS＆LT; = 2 * W + 2 * H - 5）
* PX = 0，* PY = 2 * W + 2 * H - 4 - POS;
}
无效SpiralShift（字符*一，INT W，INT高）
{
INT W0 = W;
而（并且R w 0安培;＆安培h取代; 0）
{
INT LEN = EnvelopeLength（W，H），POS机;
INT XTO，YTO，xfrom，yfrom;
对于（POS = 0; POS＆LT; LEN - 1; POS ++）
{
EnvelopePosition2Coords（安培; XTO，和放大器;音速，W，H，POS）;
EnvelopePosition2Coords（安培; xfrom，＆安培; yfrom，W，H，POS + 1）;
一个[音速* W0 + XTO] = A [yfrom * W0 + xfrom]。
}
EnvelopePosition2Coords（安培; XTO，和放大器;音速，W，H，LEN - 1）;
如果（并且R w 2＆安培;＆安培h取代; 2）
{
EnvelopePosition2Coords（安培; xfrom，＆安培; yfrom，瓦特 - 2，H - 2，0）;
一个[音速* W0 + XTO] = A [W0 + 1 + yfrom * W0 + xfrom]。
瓦特 - = 2;
ħ - = 2;
一个+ = W0 + 1;
}
其他
{
一个[音速* W0 + XTO] ='';
打破;
}
}
}
无效PrintSpiral（为const char * S，INT W，INT高）
{
INT X，Y;
看跌期权（螺旋）;
对于（Y = 0; Y＆LT; H; Y ++）
{
为（X = 0; X - 其中;瓦特; X ++）
的printf（％C，S [Y * W + X]）;
看跌期权（）;
}
看跌期权（）;
}
INT主要（无效）
{
炭spiral1x1 [1 * 1] =
一个;
炭spiral2x2 [2 * 2] =
沃
医生;
焦炭spiral5x6 [5 * 6 =
这是我
荷兰国际集团SS
lce.e
lnetna
arips;
INT I;
PrintSpiral（spiral1x1，1，1）;
对于（i = 0;我和小于1 * 1;我++）
{
SpiralShift（spiral1x1，1，1）;
PrintSpiral（spiral1x1，1，1）;
}
PrintSpiral（spiral2x2，2，2）;
对于（I = 0; I＆2 * 2;我+ +）
{
SpiralShift（spiral2x2，2，2）;
PrintSpiral（spiral2x2，2，2）;
}
PrintSpiral（spiral5x6，6，5）;
对于（I = 0; I＆小于5 * 6;我+ +）
{
SpiralShift（spiral5x6，6，5）;
PrintSpiral（spiral5x6，6，5）;
}
返回0;
}
输出（ ideone ）：
螺旋：
一个
螺旋：
螺旋：
W 0
，D R
螺旋：
要么
ð
螺旋：
R D所
螺旋：
ð
螺旋：
螺旋：
牛逼H I的I
我体中šš
L C即Ë
L N E T N一
A R I P小号
螺旋：
他的是
体中发E
I E。 N A
升C N（E T）
升A R I P小号
螺旋：
I S I S
的s简一
ñ。 Ť
I E C N（E S）
L L A R I P
螺旋：
的I个
发E N t个
克（E S）
ñ。 ËC N p
-111一个R I
螺旋：
我是个
发E N t个（E S）
ñp
G 。权证我
N I L L A R
螺旋：
I S A S
简T Eñp
小号C I
。 Ëř
克正-111一
螺旋：
ŞA S p
N t个简C I
E Eř
秒。一个
克正-111
螺旋：
A S P I
T E N c个Ëř
ñ。一个
É左
小号克正I L
螺旋：
A S P I - [R
简权证。一个
T L
立升
（E S）克正我
螺旋：
小号P I R A
ñ权证。升
É左
T I
ñ（E S）克正
螺旋：
螺旋
权证。升
N I
简
T N（E S）克
螺旋：
P I R A L L
即一世
C N
体中
ËT N（E S）
螺旋：
I R A L L I
。 ñ
例如
C
否E T N（E S）
螺旋：
R A L L I N
G
。
（E S）
C N（E T）否E
螺旋：
A L L I体中
小号
。 Ë
权证否E T N
螺旋：
L L我体中
小号
Ë
ñ
。 ËC N（E T）
螺旋：
L Iñ的s
Ë
ñ
Ť
。权证否E
螺旋：
我体中发E
ñ
Ť
Ë
。 ËC N
螺旋：
体中发Eñ
Ť
Ë
ñ
。权证
螺旋：
的s简牛逼
Ë
ñ
C
。 Ë
螺旋：
发EñT E
ñ
C
Ë
。
螺旋：
发E N t个简
C
Ë
。
螺旋：
简T E N c个
Ë
。
螺旋：
N t个简权证
。
螺旋：
T E N c个即
螺旋：
简权证。
螺旋：
ñ权证。
螺旋：
权证。
螺旋：
即
螺旋：
。
螺旋：
I want to left shift an n*n array (n is an even number ), m times like this Image :
I spent one day to find a solution, but I couldn't find a general solution.
Do you know an algorithm to solve this problem? Or any guide that can help me ?
for example(each parenthesis represents a cell in array ) :
n= 2 and m =1
before shifting :
(1) (2)
(3) (4)
after shifting :
(2) (4)
(0) (3)
Second example :
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)
解决方案
The idea is simple. You shift the outer envelope/shell, then shift the next inner and so on, until there's nothing else to shift.
Between consecutive shifts you copy the first character of the next inner envelope/shell to the last (just vacated) of the last envelope/shell. This gives you continuity, provides data flow between the envelopes/shells.
To shift a rectangular envelope by 1 position you may first count how many elements are in it (1 in 1x1, 4 in 2x2, 8 in 3x3, 12 in 4x4 and so on for squares).
And then you can run a coordinate/position along the envelope from 0 to length-2, convert it into regular coordinates within the 2d array. This will give you the position where to copy. Now, the position for the source is the very next one along the envelope and you can convert it into 2d coordinates similarly.
My implementation in 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;
}
Output (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:
相关推荐
猜您喜欢
精彩图集
