从中心顺时针扩展螺旋打印二维数组

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 循环来完成（或者只是通过一些适当的迭代并在命中矩阵单元数时停止...或命中端点角）

您需要处理 even/odd 矩阵大小

对于奇数矩阵大小，中间点很容易。对于均匀尺寸，它有点复杂。如果您使用 CW 旋转，则使用将大小减半的舍入除法结果并从向右移动开始。（如果您需要不同的螺旋，则需要将 +1 添加到 x and/or y 并更改起始方向）这样螺旋将保持居中。

所以如果你有偶数大小的矩阵那么最后一次移动是两次如果你有奇数大小那么最后一次移动只有一次（就像在这个例子中）

旋转

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

移动

也将当前位置存储为二维矢量。该运动只是将当前方向矢量添加到它。

解决这个问题很有趣...

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

Live Code

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;
    }
}

Answer 3

    int radius = 0;
    int i = centerX;
    int j = centerY;
    Debug.Log("i=" + i + "; j=" + j);
    ++i;
    radius += 2;
    while ((i < dimm) && (i >= 0))
    {
        for (int c = j; j < c + radius; j++)
            Debug.Log("i=" + i + "; j=" + j);
        --j;
        --i;
        for (int c = i; i > c - radius + 1; i--)
            Debug.Log("i=" + i + "; j=" + j);
        if (i < 0)
            break;
        else
            Debug.Log("i=" + i + "; j=" + j);
        --j;
        for (int c = j; j > c - radius; j--)
            Debug.Log("i=" + i + "; j=" + j);
        ++i;
        ++j;
        for (int c = i; i < c + radius; i++)
            Debug.Log("i=" + i + "; j=" + j);
        radius += 2;
    }

此代码将从自定义中心（CenterX，CenterY）输出逆时针平方矩阵（dimm X dimm）索引；最后，如果它来自矩阵大小。

Answer 4

bool IsIterationComplete(int iteration, int nCenter, std::vector<std::vector<bool>>& vVisited)
{
    int nHigh = nCenter+iteration;
    int nLow = nCenter-iteration;
    //cout<<endl<<"High "<<nHigh<<"Low "<<nLow<<endl;
    for(int i=nLow;i<=nHigh;i++)
    {
        if(!vVisited[nHigh][i] || !vVisited[nLow][i]) 
            return false;
    }

    for(int i=nLow;i<=nHigh;i++)
    {
        if(!vVisited[i][nHigh] || !vVisited[i][nLow])
            return false;
    }

    return true;
}
void PrintSpiral(std::vector<std::vector<int>>& vMat,std::vector<std::vector<bool>>& vVisited, int row, int col, int nCenter, int iteration)
{
    cout<<vMat[row][col];
    vVisited[row][col]=true;

    if(row==0 && col==0)
        return;

    if(IsIterationComplete(iteration,nCenter,vVisited))
        iteration++;

    //cout<<endl<<"row "<<row<<" column "<<col<<"Iteration "<<iteration<<endl;

//left
    if(col-1>=0 && !vVisited[row][col-1] && col-1>=nCenter-iteration)
    {
        cout<<"Left "<<endl;
        PrintSpiral(vMat,vVisited,row,col-1,nCenter,iteration);
    }

    //Down
    if((row+1)<vMat.size() && !vVisited[row+1][col] && row+1<=nCenter+iteration)
    {
        cout<<"Down "<<endl;
        PrintSpiral(vMat,vVisited,row+1,col,nCenter,iteration);
    }

    //right
    if((col+1)<vMat.size() && !vVisited[row][col+1] && col+1<=nCenter+iteration)
    {
        cout<<"Right "<<endl;
        PrintSpiral(vMat,vVisited,row,col+1,nCenter,iteration);
    }

    //up    
    if(row-1>=0 && !vVisited[row-1][col] && row-1>=nCenter-iteration)
    {
        cout<<"Up "<<endl;
        PrintSpiral(vMat,vVisited,row-1,col,nCenter,iteration);
    }
}


int main (int argc, const char * argv[])
{
    int nCount=1;
    std::vector<std::vector<int>> vMat;
    std::vector<std::vector<bool>> vVisited;
    for(int i=0; i<7; i++)
    {
        std::vector<int> row;
        std::vector<bool> visitedRow;
        for(int j=0; j<7; j++)
        {
            row.push_back(nCount);
            cout<<nCount<<'\t';
            nCount++;
            visitedRow.push_back(false);
        }
        cout<<'\n';
        vMat.push_back(row);
        vVisited.push_back(visitedRow);
    }
    cout<<'\n';
    PrintSpiral(vMat,vVisited,vMat.size()/2,vMat.size()/2,vMat.size()/2,0);
    return 0;
}

从中心顺时针扩展螺旋打印二维数组

Print 2-D Array in clockwise expanding spiral from center

c++

algorithm

loops

2d

matrix