【Leetcode】54. Spiral Matrix（模拟）-蒲公英云

【Leetcode】54. Spiral Matrix（模拟）

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

Example 1:

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

Example 2:

Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

题目大意：

题目要求我们依照顺时针方向（右，下，左，上），来遍历整个二维矩阵。将其按照一维数组输出。

解题思路：

我们只需要控制好方向即可，将判断是否更改前进方向的标准设置为：1、是否超出二维矩阵本身。2、收否已经被遍历过。

可以使用搜索，也可以直接用while循环。注意在判断是否已经被遍历过时，可以初始化另外一个辅助数组。

class Solution {
private:
    int g[4][2] = {
   {0,1},{1,0},{0, -1},{-1,0}};
    vector<int> ans;
    vector<vector<bool> > map;
    int n,m;
    int dir;
    void dfs(int x, int y, vector<vector<bool> > map, vector<vector<int> > matrix){
        if(ans.size()==m*n){
            return ;
        }
        int cor_x = x + g[dir][0];
        int cor_y = y + g[dir][1];
        if (valid(cor_x, cor_y, map) == false){
            dir = (dir+1)%4;
            cor_x = x + g[dir][0];
            cor_y = y + g[dir][1];
        }
        ans.push_back(matrix[cor_x][cor_y]);
        map[cor_x+1][cor_y+1] = true;
        dfs(cor_x, cor_y, map, matrix);    
        if(ans.size()==m*n){
            return ;
        }
    }     
    bool valid(int x, int y, vector<vector<bool> > map){
        if (x<n&&x>=0&&y>=0&&y<m&&map[x+1][y+1]==false){
            return true;
        }
        return false;
    }
public:
    vector<int> spiralOrder(vector<vector<int> >& matrix) {
        if (matrix.size() == 0){
            return ans;
        }
        n = matrix.size();
        m = matrix[0].size();
        for(int i = 0; i<n+2;i++){
            vector<bool> v;
            for (int j = 0; j<m+2;j++){
                v.push_back(false);
            }
            map.push_back(v);
        } 
        ans.push_back(matrix[0][0]);
        map[1][1] = true;
        dir = 0;
        dfs(0,0,map, matrix);
        return ans;
    }
};