对付所有的旋转矩阵

**54、Spiral Matrix **
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

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

You should return [1,2,3,6,9,8,7,4,5].
或者
**59、Spiral Matrix II **
Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,
You should return the following matrix:

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

解答技巧：
对付所有的旋转矩阵类的问题，最重要的就是扫描策略，以及判断下一行是否存在。
我们采取的扫描策略是：横向的行所有的都扫描，纵向的行只扫描夹在行中间的。
比如先扫：1 2 3，然后再扫：4，然后再扫：5 6 7，再扫：8

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> rec;
        if(matrix.empty()||matrix[0].empty()) //判断矩阵是否为空的方法
          return rec;
        int m = matrix.size();
        int n = matrix[0].size();
        int t = (min(m,n)-1)/2;
        int k=0;
        while(k<=t)
        {   
            for(int j=k;j<n-k;j++)
              rec.push_back(matrix[k][j]);


            for(int i=k+1;i<m-1-k;i++)
               rec.push_back(matrix[i][n-1-k]);

            if(m-1-k>k)  //必须存在
            for(int j=n-1-k;j>=k;j--)
               rec.push_back(matrix[m-1-k][j]);

            if(k<n-k-1)  //必须存在
            for(int i=m-2-k;i>k;i--)
               rec.push_back(matrix[i][k]);

            k++;
        }   
        return rec;  
    }
};

特别要注意的是下面两行条件判断的代码：

            if(m-1-k>k)  //必须存在
            for(int j=n-1-k;j>=k;j--)
               rec.push_back(matrix[m-1-k][j]);

            if(k<n-k-1)  //必须存在
            for(int i=m-2-k;i>k;i--)
               rec.push_back(matrix[i][k]);

如果存在第三次扫描，则最下面一行必须要存在，也就是说：m-1-k>k，这样才能说下一行存在，必须判断矩阵的行数是否足够
比如说对于矩阵：

1  2  3
6  5  4

如果存在第四次扫描，则最后一行即最左边的一行必须存在，也就是说：k<n-1-k，这样才能说最后一行存在，必须判断矩阵的列数是否足够
比如说对于矩阵：

1  2
6  3
5  4

总之，就是要判断矩阵的行数必须大于两行，列数必须大于两列，才会有第三和第四次扫描的存在。

算法：

54. Spiral Matrix

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> rec;
        if(matrix.empty()||matrix[0].empty()) //判断矩阵是否为空的方法
          return rec;
        int m = matrix.size();
        int n = matrix[0].size();
        int t = (min(m,n)-1)/2;
        int k=0;
        while(k<=t)
        {   
            for(int j=k;j<n-k;j++)
              rec.push_back(matrix[k][j]);

            for(int i=k+1;i<m-1-k;i++)
               rec.push_back(matrix[i][n-1-k]);

            if(m-1-k>k)  //行必须存在
            for(int j=n-1-k;j>=k;j--)
               rec.push_back(matrix[m-1-k][j]);

            if(k<n-k-1)  //列必须存在
            for(int i=m-2-k;i>k;i--)
               rec.push_back(matrix[i][k]);

            k++;
        }   
        return rec;  
    }
};

59. Spiral Matrix II

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<int> temp(n,0);
        vector<vector<int>> rec(n,temp);
        if(n<=0)
          return rec;
        int t= (n-1)/2;
        int k = 0;
        int N = 0;
        
        while(k<=t)
        {
            for(int j=k;j<=n-1-k;j++)
              rec[k][j] = ++N;
            
            for(int i=k+1;i<=n-2-k;i++)
              rec[i][n-1-k] = ++N;
              
            if(n-1-k>k)
            for(int j=n-1-k;j>=k;j--)
              rec[n-1-k][j] = ++N;
              
            if(k<n-1-k)
            for(int i=n-2-k;i>=k+1;i--)
              rec[i][k] = ++N;
            
            k++;
        }
        return rec;
    }
};

剑指offer

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> rec;
        if(matrix.empty()||matrix[0].empty())
            return rec;
        int m = matrix.size();
        int n = matrix[0].size();
        
        int k = 0;
        
        while(2*k<min(m,n)){
            
            for(int j=k;j<n-k;j++){
                rec.push_back(matrix[k][j]);
            }
            for(int i=k+1;i<m-k;i++){
                rec.push_back(matrix[i][n-k-1]);
            }
            
            if(m-k-1>k){
                for(int j=n-k-2;j>=k;j--){
                    rec.push_back(matrix[m-k-1][j]);
                }
            }
            if(k<n-k-1){
                for(int i=m-k-2;i>k;i--){
                    rec.push_back(matrix[i][k]);
                }
            }
            k++;
            
        }
        return rec;
    }
};