学步园

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

Given an integer n, generate a square matrix filled with elements from 1 ton² in spiral order.

For example,
Given n = 3,

You should return the following matrix:

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

思路：

光标转移有四个状态，依次是向右，向下，向左，向上。光标转移状态的变化根据三个条件：1. 到达上界（n）2.到达下界（0）3.光标的下一个位置已经被填满。据此编码。

题解：

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        enum { VISITED = -1 };  
        
        if (matrix.size()==0)
            return vector<int>();
            
        const int M = matrix.size();
        const int N = matrix[0].size();
        
        int cursorX = 0;  
        int cursorY = 0;  
          
        int incrX = 1;  
        int incrY = 0;  
          
        int nextX, nextY;  
        
        int LEFT = 0, RIGHT = N;
        int TOP = 0, BOTTOM = M;
          
        auto valid_X=[&](const int c) -> bool {  
            return c >= LEFT && c < RIGHT;  
        };  
        
        auto valid_Y=[&](const int c) -> bool {
            return c >= TOP && c < BOTTOM ;
        };
          
        auto valid_state=[&]()->bool {  
            return valid_X(nextX) && valid_Y(nextY);
        };  
          
        auto next_state=[&]() {  
            switch(incrX * 2 + incrY)
            {
                case 2: // moving right
                    ++TOP;
                    incrX = 0, incrY = 1;
                    break;
                case -2: // moving left
                    --BOTTOM;
                    incrX = 0, incrY = -1;
                    break;
                case 1: // moving down
                    --RIGHT;
                    incrX = -1, incrY = 0;
                    break;
                case -1: // moving up
                    ++LEFT;
                    incrX = 1, incrY = 0;
                    break;
            }
        };  
          
        auto next_pos=[&]() {  
            nextX = cursorX + incrX;  
            nextY = cursorY + incrY;  
        };
        
        vector<int> ret;
        ret.reserve(M * N);
        for(int i = 0; i < M * N; ++i)
        {
            ret.push_back(matrix[cursorY][cursorX]);

            next_pos();
            if (!valid_state())  
            {  
                next_state();  
                next_pos();  
            } 
            
            cursorX = nextX;
            cursorY = nextY;
        }
        
        return ret;
    }
};

class Solution {
public:
    vector<vector<int> > generateMatrix(int n) {
        enum { UNUSED = -1 };
        
        vector<vector<int>> matrix(n);
        for(auto& row : matrix)
        {
            row.resize(n);
            fill(begin(row), end(row), UNUSED);
        }
        
        int cursorX = 0;
        int cursorY = 0;
        
        int incrX = 0;
        int incrY = 1;
        
        int nextX, nextY;
        
        auto valid_pos=[&](const int c) -> bool {
            return c >= 0 && c < n;
        };
        
        auto valid_state=[&]()->bool {
            return valid_pos(nextX) && 
                valid_pos(nextY) &&
                matrix[nextX][nextY] == UNUSED;
        };
        
        auto next_state=[&]() {
            switch(incrX * 2 + incrY)
            {
                case 1:
                    incrX = 1, incrY = 0;
                    break;
                case 2:
                    incrX = 0, incrY = -1;
                    break;
                case -1:
                    incrX = -1, incrY = 0;
                    break;
                case -2:
                    incrX = 0, incrY = 1;
                    break;
            }
        };
        
        auto next_pos=[&]() {
            nextX = cursorX + incrX;
            nextY = cursorY + incrY;
        };
        
        for(int i = 1; i <= n * n; ++i)
        {
            matrix[cursorX][cursorY] = i;
            
            // increment the cursor
            next_pos();
            if (!valid_state())
            {
                next_state();
                next_pos();
            }
            
            cursorX = nextX;
            cursorY = nextY;
        }
        
        return matrix;
    }
};