从中心顺时针旋转螺旋打印2-D阵列

Question

我保证是一个完美的方阵.我想在这种情况下从矩阵的中心开始matrix[2][2],我知道如何计算中心(int)(dimensions / 2).我需要以下面的向外螺旋模式输出数组的内容.当然,算法应该适用于任何完美的方阵.我不确定这个算法是否已经存在,我不想重新发明轮子.

int dimensions / 2;

21 22 23 24 25
20 7  8  9  10
19 6  1  2  11
18 5  4  3  12 
17 16 15 14 13

这个例子的输出应该是

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Answer 1

因为这闻起来像作业，所以没有任何代码或直接答案，而只是一些提示：

您可以将其视为乌龟问题：

让我们沿着细胞m移动，1并沿螺旋方向（顺时针或逆时针）r旋转90角度。然后可以将螺旋编码为一系列乌龟命令，从而形成该模式（从起点开始）：

    m,r,m,r, 
    m,m,r,m,m,r,
    m,m,m,r,m,m,m,r,
    m,m,m,m,r,m,m,m,m,r,
    m,m,m,m,m,r 

如您所见，您从1x移动开始，然后在两次重复之后旋转，您切换到2x移动，在2移动之后切换到3x移动，...等等。只需很少的for循环即可完成此操作（或只需进行一些适当的迭代即可完成，并在命中矩阵数量的单元格...或命中端点角时停止）

您需要处理偶数/奇数矩阵大小

对于奇数矩阵大小，中间点很容易。对于偶数大小，它要复杂一些。如果您使用CW旋转，则使用将大小减半的舍入后的除法结果，然后从向右移动开始。（如果需要不同的螺旋则需要添加+1到x和/或y与改变起动方向），这样所述螺旋将保持居中。

因此，如果矩阵大小为偶数，那么如果大小为奇数，则最后一次移动是两次，而最后一次运动只有一次（如本例所示）

回转

将方向存储为2D矢量。例如d=(+1,0)表示正确。要旋转2D向量，您只需交换坐标并取反一个轴（这意味着CW / CCW）。例如(x,y) -> (y,-x)

运动

也将当前位置存储为2D向量。该运动只是向其添加当前方向向量。

乐于解决这个问题...

Answer 2

让我们首先确定模式..

偶数方形矩阵,例如:4x4

  07 > 08 > 09 > 10
  ^               v
  06  (01)> 02   11
  ^          v    v
  05 < 04 < 03   12
                  v
 [16]< 15 < 14 < 13

Starting Point: [2, 2] ~ [SIZE/2, SIZE/2]

Ending Point: [4, 1] ~ [SIZE, 1]

Chains: Count(K-chain)=2 for K = 1..(SIZE-2)
        + 3 for Count = SIZE-1

奇数方形矩阵,例如:5x5

  21 > 22 > 23 > 24 >[25]
  ^
  20   07 > 08 > 09 > 10
  ^    ^               v
  19   06  (01)> 02   11
  ^    ^          v    v
  18   05 < 04 < 03   12 
  ^                    v
  17 < 16 < 15 < 14 < 13

Starting Point: [2, 2] ~ [?SIZE/2?, ?SIZE/2?]

Ending Point: [1, 5] ~ [1, SIZE]

Chains: Count(K-chain)=2 for K = 1..(SIZE-2)
        + 3 for Count = SIZE-1

现场代码

void print_spiral (int ** matrix, int size)
{
    int x = 0; // current position; x
    int y = 0; // current position; y
    int d = 0; // current direction; 0=RIGHT, 1=DOWN, 2=LEFT, 3=UP
    int c = 0; // counter
    int s = 1; // chain size

    // starting point
    x = ((int)floor(size/2.0))-1;
    y = ((int)floor(size/2.0))-1;

    for (int k=1; k<=(size-1); k++)
    {
        for (int j=0; j<(k<(size-1)?2:3); j++)
        {
            for (int i=0; i<s; i++)
            {
                std::cout << matrix[x][y] << " ";
                c++;

                switch (d)
                {
                    case 0: y = y + 1; break;
                    case 1: x = x + 1; break;
                    case 2: y = y - 1; break;
                    case 3: x = x - 1; break;
                }
            }
            d = (d+1)%4;
        }
        s = s + 1;
    }
}