leetcode热题100（54. 螺旋矩阵）c++

链接：54. 螺旋矩阵 - 力扣（LeetCode）

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

思路

因为顺时针遍历，最简单的想法就是dfs遍历一遍，只要我们遇到边界条件或已经遍历过的点，直接换一个方向接着遍历即可，只会存在一个方法是没遍历过的，直到容器的大小为n*m那么说明整个数组已经遍历了一遍

代码

class Solution {
public:
    int st[12][12];
    int dx[4]={-1,0,1,0};
    int dy[4]={0,-1,0,1};
    int n,m;
    vector<int> res;
    vector<int> spiralOrder(vector<vector<int>>& g) {
        n = g.size();
        m = g[0].size();
        st[0][0]=true;
        res.push_back(g[0][0]);
        dfs(0,0,3,g);
        return res;
    }

    void dfs(int x,int y,int op,vector<vector<int>>& g){
        if(res.size()>=n*m) return;
        int tx = x+dx[op];
        int ty = y+dy[op];
        if(tx<0||tx>=n||ty<0||ty>=m||st[tx][ty]){
            for(int i=0;i<4;i++){
                tx = x+dx[i];
                ty = y+dy[i];
                if(tx<0||tx>=n||ty<0||ty>=m||st[tx][ty]) continue;
                else{
                    res.push_back(g[tx][ty]);
                    st[tx][ty]=true;
                    dfs(tx,ty,i,g);
                    return;
                }
            }
        }else{
            res.push_back(g[tx][ty]);
            st[tx][ty]=true;
            dfs(tx,ty,op,g);
        }
    }

};