[经典面试题]蛇形矩阵（螺旋矩阵）

【1.打印蛇形矩阵】

Given a matrix ofmxnelements (mrows,ncolumns), 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].

【代码】

    /**------------------------------------
    *   日期：2015-02-05
    *   作者：SJF0115
    *   题目: 54.Spiral Matrix
    *   网址：https://oj.leetcode.com/problems/spiral-matrix/
    *   结果：AC
    *   来源：LeetCode
    *   博客：
    ---------------------------------------**/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;

    class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int> > &matrix) {
            vector<int> result;
            if(matrix.empty()){
                return result;
            }//if
            int row = matrix.size();
            int col = matrix[0].size();
            int count = row * col;
            int index = 1;
            int beginX = 0,endX = row - 1;
            int beginY = 0,endY = col - 1;
            while(index <= count){
                // right
                for(int i = beginY;i <= endY;++i){
                    result.push_back(matrix[beginX][i]);
                    ++index;
                }//for
                ++beginX;
                if(beginX > endX){
                    break;
                }//if
                // down
                for(int i = beginX;i <= endX;++i){
                    result.push_back(matrix[i][endY]);
                    ++index;
                }//for
                --endY;
                if(endY < beginY){
                    break;
                }//if
                // left
                for(int i = endY;i >= beginY;--i){
                    result.push_back(matrix[endX][i]);
                    ++index;
                }//for
                --endX;
                if(endX < beginX){
                    break;
                }//if
                // up
                for(int i = endX;i >= beginX;--i){
                    result.push_back(matrix[i][beginY]);
                    ++index;
                }
                ++beginY;
                if(beginX > endY){
                    break;
                }//if
            }//while
            return result;
        }
    };

    int main(){
        Solution s;
        vector<vector<int> > matrix = {{1,2,3},{4,5,6},{7,8,9}};
        vector<int> result = s.spiralOrder(matrix);
        // 输出
        for(int i = 0;i < result.size();++i){
            cout<<result[i]<<"  ";
        }//for
        cout<<endl;
        return 0;
    }

【2.生成蛇形矩阵】

Given an integern, generate a square matrix filled with elements from 1 ton2in spiral order.

For example,
Givenn=3,

You should return the following matrix:

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

【代码二】

    /**------------------------------------
    *   日期：2015-02-05
    *   作者：SJF0115
    *   题目: 59.Spiral Matrix II
    *   网址：https://oj.leetcode.com/problems/spiral-matrix-ii/
    *   结果：AC
    *   来源：LeetCode
    *   博客：
    ---------------------------------------**/
   class Solution {
    public:
        vector<vector<int> > generateMatrix(int n) {
            vector<vector<int> > matrix(n,vector<int>(n,0));
            if(n <= 0){
                return matrix;
            }//if
            int count = n * n;
            int index = 1;
            int beginX = 0,endX = n - 1;
            int beginY = 0,endY = n - 1;
            while(index <= count){
                // right
                for(int i = beginY;i <= endY;++i){
                    matrix[beginX][i] = index;
                    ++index;
                }//for
                ++beginX;
                // down
                for(int i = beginX;i <= endX;++i){
                    matrix[i][endY] = index;
                    ++index;
                }//for
                --endY;
                // left
                for(int i = endY;i >= beginY;--i){
                    matrix[endX][i] = index;
                    ++index;
                }//for
                --endX;
                // up
                for(int i = endX;i >= beginX;--i){
                    matrix[i][beginY] = index;
                    ++index;
                }
                ++beginY;
            }//while
            return matrix;
        }
    };

【代码三】

    /**------------------------------------
    *   日期：2015-02-04
    *   作者：SJF0115
    *   题目: 59.Spiral Matrix II
    *   网址：https://oj.leetcode.com/problems/spiral-matrix-ii/
    *   结果：AC
    *   来源：LeetCode
    *   博客：
    ---------------------------------------**/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;

    class Solution {
    public:
        vector<vector<int> > generateMatrix(int n) {
            vector<vector<int> > matrix(n,vector<int>(n,0));
            if(n <= 0){
                return matrix;
            }//if
            int count = n * n;
            int index = 1;
            int x = 0,y = -1;
            while(index <= count){
                // right
                ++y;
                while(y < n && matrix[x][y] == 0){
                    matrix[x][y++] = index;
                    ++index;
                }//while
                --y;
                // down
                ++x;
                while(x < n && matrix[x][y] == 0){
                    matrix[x++][y] = index;
                    ++index;
                }//while
                --x;
                // left
                --y;
                while(y >= 0 && matrix[x][y] == 0){
                    matrix[x][y--] = index;
                    ++index;
                }//while
                ++y;
                // up
                --x;
                while(x >= 0 && matrix[x][y] == 0){
                    matrix[x--][y] = index;
                    ++index;
                }//while
                ++x;
            }//while
            return matrix;
        }
    };

    int main(){
        Solution s;
        int n = 5;
        vector<vector<int> > matrix = s.generateMatrix(n);
        // 输出
        for(int i = 0;i < n;++i){
            for(int j = 0;j < n;++j){
                cout<<matrix[i][j]<<"  ";
            }//for
            cout<<endl;
        }//for
        return 0;
    }