54. Spiral Matrix (Medium)

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

For example,
Given the following matrix:

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

You should return [1,2,3,6,9,8,7,4,5].

Solution:

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

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

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> res;
    if (matrix.empty() || matrix[0].empty()) return res;
    int m = matrix.size(), n = matrix[0].size();
    int c = m < n ? (m+1)/2 : (n+1)/2; // layer
    int p = m, q = n; // row, col
    for (int i = 0; i < c; ++i, p -= 2, q -= 2) { // loop by layer
        for (int col = i; col < i+q; ++col)
            res.push_back(matrix[i][col]);
        for (int row = i+1; row < i+p; ++row)
            res.push_back(matrix[row][i+q-1]);

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

        for (int col = i+q-2; col >= i; --col)
            res.push_back(matrix[i+p-1][col]);
        for (int row = i+p-2; row > i; --row)
            res.push_back(matrix[row][i]);
    }
    return res;
}