How to read a char matrix anticlockwise in C++?

Question

So my input should be a nxn (n<=20) matrix of words which do not exceed 9 characters each. The output should be a string sentence, formed by reading the matrix in an clockwise spiral way starting from the top left corner. With some help, I managed to get it to work.. though I still have some trouble fully comprehending what's exactly going on. I have absolutely no idea how to do it the other way around though - anticlockwise spiral starting from the bottom right corner. Here's my code so far:

    string s;
    int hor = 0, vert = 0;
    while (hor < n / 2 && vert < n / 2)
    {
        for (i = vert; i < n - vert; i++)
            s = s + a[hor][i] + " ";
        for (i = hor + 1; i < n - hor; i++)
            s = s + a[i][n - vert - 1] + " ";
        for (i = n - vert - 2; i >= vert; i--)
            s = s + a[n - hor - 1][i] + " ";
        for (i = n - hor - 2; i > hor; i--)
            s = s + a[i][vert] + " ";
        hor++;
        vert++;
    }
    if (n % 2)
        for (i = vert; i < n - vert; i++)
            s = s + a[hor][i] + " ";
    else
        for (i = hor; i < n - hor; i++)
            s = s + a[i][vert] + " ";
    cout << s << endl;

Any ideas? And is there not some easier way to do this?

Answer 1

1. Use variables x and y for your position, easier to track that way.
2. Use a state variable to track your direction. Counter-clockwise is left, up, right, then down.
3. Add a word from each position.
4. Advance your position until you hit an edge, then change direction. Do this four times (once for each direction), then increment an edge counter, representing the width of your spiral.
5. When you've done this 400 times (20*20), you are done.

The code flows directly from that algorithm. (Note, I haven't compiled this, so you'll have to check for errors yourself).

int x = n - 1; // Start at right.
int y = n - 1; // Start at bottom.
int spiral = 0; // Track the edges already visited (spiral).
int direction = 0; // 0=left, 1=up, 2=right, 3=down.  You could also use an enum.
string s; // String builder.

for (int count = 0; count < 400; count++) { // One word per cell, 400 cells.
  s = s + a[x][y] + " "; // Add the word.
  if (direction == 0) { // Left
    if (x > spiral) x--; // Check edge, advance if no edge.
    else { y--; direction = 1; } // Change direction to up if edge is hit.
  } else if (direction == 1) { // Up
    if (y > spiral) y--; // Check edge, advance if no edge.
    else { x++; direction = 2; } // Change direction to right if edge is hit.
  } else if (direction == 2) { // Right
    if (x < (n - 1) - spiral) x++; // Check edge, advance if no edge.
    else { y++; direction = 3; spiral++; } // Change edge and direction to down.      
  } else if (direction == 3) { // Down
    if (y < (n - 1) - spiral) y++; // Check edge, advance if no edge.
    else { x--; direction = 0; } // Change direction to left if hit.
  }
}

Answer 2

Associate every cell (x,y) with a distance and an angle:

 d(x,y) = max(abs(x - N/2), abs(y - N/2))
 a(x,y) = atan2(y - N/2, x - N/2) + bias;

Then sort your data first based on distance, next on angle -- the order is well defined. A combined metric would use e.g. d(x,y) * 1000 + (int)a(x,y); to perform the sort in a single pass.

(Disclaimer -- this is more or less language agnostic)