【Leetcode】54. Spiral Matrix（模拟）

超、凢脫俗 2022-03-01 14:42 179阅读 0赞

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;
        }
    };