[LeetCode] Spiral Matrix 螺旋矩阵

Given a matrix of m x n elements (m rows, ncolumns), 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]

这道题让我们搓一个螺旋丸，将一个矩阵按照螺旋顺序打印出来，只能一条边一条边的打印，首先要从给定的 mxn 的矩阵中算出按螺旋顺序有几个环，注意最中间的环可以是一个数字，也可以是一行或者一列。环数的计算公式是 min(m, n) / 2，知道了环数，就可以对每个环的边按顺序打印，比如对于题目中给的那个例子，个边生成的顺序是(用颜色标记了数字，Github 上可能无法显示颜色，请参见博客园上的帖子) Red -> Green -> Blue -> Yellow -> Black

1　2　3

7　8　

定义 p，q 为当前环的高度和宽度，当p或者q为1时，表示最后一个环只有一行或者一列，可以跳出循环。此题的难点在于下标的转换，如何正确的转换下标是解此题的关键，可以对照着上面的 3x3 的例子来完成下标的填写，代码如下：

解法一：

class Solution {

public:

    vector<int> spiralOrder(vector<vector<int> > &matrix) {

        if (matrix.empty() || matrix[].empty()) return {};

        int m = matrix.size(), n = matrix[].size();

        vector<int> res;

        int c = m > n ? (n + ) /  : (m + ) / ;

        int p = m, q = n;

        for (int i = ; i < c; ++i, p -= , q -= ) {

            for (int col = i; col < i + q; ++col)

                res.push_back(matrix[i][col]);

            for (int row = i + ; row < i + p; ++row)

                res.push_back(matrix[row][i + q - ]);

            if (p ==  || q == ) break;

            for (int col = i + q - ; col >= i; --col)

                res.push_back(matrix[i + p - ][col]);

            for (int row = i + p - ; row > i; --row)

                res.push_back(matrix[row][i]);

        }

        return res;

    }

};

如果觉得上面解法中的下标的转换比较难弄的话，也可以使用下面这种坐标稍稍简洁一些的方法。对于这种螺旋遍历的方法，重要的是要确定上下左右四条边的位置，那么初始化的时候，上边 up 就是0，下边 down 就是 m-1，左边 left 是0，右边 right 是 n-1。然后进行 while 循环，先遍历上边，将所有元素加入结果 res，然后上边下移一位，如果此时上边大于下边，说明此时已经遍历完成了，直接 break。同理对于下边，左边，右边，依次进行相对应的操作，这样就会使得坐标很有规律，并且不易出错，参见代码如下：

解法二：

class Solution {

public:

    vector<int> spiralOrder(vector<vector<int>>& matrix) {

        if (matrix.empty() || matrix[].empty()) return {};

        int m = matrix.size(), n = matrix[].size();

        vector<int> res;

        int up = , down = m - , left = , right = n - ;

        while (true) {

            for (int j = left; j <= right; ++j) res.push_back(matrix[up][j]);

            if (++up > down) break;

            for (int i = up; i <= down; ++i) res.push_back(matrix[i][right]);

            if (--right < left) break;

            for (int j = right; j >= left; --j) res.push_back(matrix[down][j]);

            if (--down < up) break;

            for (int i = down; i >= up; --i) res.push_back(matrix[i][left]);

            if (++left > right) break;

        }

        return res;

    }

};

若对上面解法中的多个变量还是晕的话，也可以使用类似迷宫遍历的方法，这里只要设定正确的遍历策略，还是可以按螺旋的方式走完整个矩阵的，起点就是（0，0）位置，但是方向数组一定要注意，不能随便写，开始时是要往右走，到了边界或者访问过的位置后，就往下，然后往左，再往上，所以 dirs 数组的顺序是右->下->左->上，由于原数组中不会有0，所以就可以将访问过的位置标记为0，这样再判断新位置的时候，只要其越界了，或者是遇到0了，就表明此时需要转弯了，到 dirs 数组中去取转向的 offset，得到新位置，注意这里的 dirs 数组中取是按循环数组的方式来操作，加1然后对4取余，按照这种类似迷宫遍历的方法也可以螺旋遍历矩阵，参见代码如下：

解法三：

class Solution {

public:

    vector<int> spiralOrder(vector<vector<int>>& matrix) {

        if (matrix.empty() || matrix[].empty()) return {};

        int m = matrix.size(), n = matrix[].size(), idx = , i = , j = ;

        vector<int> res;

        vector<vector<int>> dirs{{, }, {, }, {, -}, {-, }};

        for (int k = ; k < m * n; ++k) {

            res.push_back(matrix[i][j]);

            matrix[i][j] = ;

            int x = i + dirs[idx][], y = j + dirs[idx][];

            if (x <  || x >= m || y <  || y >= n || matrix[x][y] == ) {

                idx = (idx + ) % ;

                x = i + dirs[idx][];

                y = j + dirs[idx][];

            }

            i = x;

            j = y;

        }

        return res;

    }

};