c++algorithmloopsmatrix2d

Print 2-D Array in clockwise expanding spiral from center


I have an guaranteed to be a perfect square matrix. I want to start at the center of the matrix in this case it would be matrix[2][2], I know how to figure the center (int)(dimensions / 2). I need to output the contents of the array in this following outward spiral pattern. Of course the algorithm should work with any perfect square matrix. I wasn't sure if this algorithm already existed and I didn't want to re-invent the wheel.

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

The output for this example should be

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

Solution

  • Let's identify the patterns first ..

    Even-Size Square Matrix, Example: 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
    

    Odd-Size Square Matrix, Example: 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;
        }
    }