题目内容

给你一个 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]

提示

1、m == matrix.length
2、n == matrix[i].length
3、1 <= m, n <= 10
4、-100 <= matrix[i][j] <= 100

题解

本题是一道比较经典的题目，重点考察对矩阵的遍历以及边界值的判断。

首先，要解此题，需要定义四个方向，然后每次炒朝一个方向走，走到头通过判定然后推到另一个方向，最终走到不能走为止。因为是顺时针的螺旋顺序，因此方向依次为→↓←↑。

我们来定义一下四个方向，如下图：

具体，请看代码注释。

代码

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        //定义四个方向，然后根据越界和是否走过两个指标判断是否应该走下一个方向，最终遍历完毕整个矩阵
        vector<int> res;//首先，定义答案
        int n = matrix.size();//获得矩阵的尺寸
        if (!n) return res;
        int m = matrix[0].size();//获得矩阵的尺寸

        int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; //定义一个方向数组
        vector<vector<bool>> st(n,vector<bool>(m));//定义一个判重数组

        for(int i = 0, x = 0, y = 0, d = 0; i < n * m; i++){
            //左上角，x = 0，y = 0。d代表方向。
            res.push_back(matrix[x][y]);
            st[x][y] = true;

            int a = x + dx[d], b = y + dy[d];
          	//判断a是否越界或者b是否越界或者matrix[a][b]是否被走过
            if(a < 0 || a >= n || b < 0 || b >= m || st[a][b]){
                d = (d + 1) % 4;//d一定在0，1，2，3内部循环。
                a = x + dx[d], b = y + dy[d];
            }
            x = a, y = b;
        }
        return res;
    }
};