Sentence Spiral 0 1 2 3 4 0 Y _ _ _ Z 1 _ _ _ _ _ 2 _ _ _ _ _ 3 _ _ _ _ _ 4 X _ _ _ Q n = 5 0 1 0 Y Z 1 X Q n = 2 Bottom left corner is Row n-1 Col 0 Top left corner is Row 0 Col 0 Top right corner is Row 0 col n-1 Bottom right corner is Row n-1 Col n-1 MLKJI NWVUH OXYTG PQRSF ABCDE The two important questions we have to ask ourselves: 1. When do we change direction? 2. How do we change direction? Since we're moving counterclockwise, every time we make a turn we always turn left. I start by moving East. East, turns left and becomes North. North turns left and becomes West. West turns left and becomes South. South turns left and becomes East. If I'm moving East and my present square is M[r][c], what is my next one? M[r][c+1] If I'm moving north and my present square is M[r][c], what is my next square? M[r-1][c] If i'm moving west and my present square is M[r][c], what is my next square? M[r][c-1] If I'm moving south and my present square is M[r][c], what is my next square? M[r+1][c]. So, if I keep track of the direction I'm moving, and my present row and column, I can easily the next square I need to place a character. When do we change direction? One way is to check if the next square is either out of bounds or already has something in it. If that's the case, I have to turn left. But there are other ways, too. If n=5, I'm at the bottom left moving east, how many symbols do I place before I have to turn left? 5 Then I turn left, how many new symbols before I have to turn left again? 4, 4, 3, 3, 2, 2, 1, 1 5, 4, 4, 3, 3, 2, 2, 1, 1 6, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1 3, 2, 2, 1, 1 n, n-1, n-1, n-2, n-2, n-3, n-3, ..., 2, 2, 1, 1 if dr describes how the row changes and dc describes how the column changes, then begin dr = 0 and dc = 1. Think of as a vector. It begins at <0,1> 0 -1 dr = newdr 1 0 dc = newdc newdr = -dc newdc = dr East: <0,1> North: <-1,0> West: <0,-1> South: <1,0> If my current square is M[r][c], my next one is M[r+dr][c+dc] If I'm moving north and my current square is M[5][7], my next one will be M[5+-1][7+0] = M[4][7]. With this technique, you don't actually have to keep track of the direction moving because "math" will do that for you. Use dr and dc to indicate direction, and turn left using the above formula.