54. Spiral Matrix

O(mn) time O(mn) space

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return {};
        int dr[] = {0, 1, 0, -1}, dc[] = {1, 0, -1, 0}, m = matrix.size(), n = matrix[0].size(), sz = m * n;
        vector<int> res;
        vector<vector<bool>> v(m, vector<bool>(n));
        int r = 0, c = 0, i = 0;
        while (sz-- > 0) {
            res.push_back(matrix[r][c]);
            v[r][c] = true;
            r += dr[i];
            c += dc[i];
            if (r < 0 || r >= m || c < 0 || c >= n || v[r][c]) {
                r -= dr[i];
                c -= dc[i];
                i = (i + 1) % 4;
                r += dr[i];
                c += dc[i];
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return {};
        int m = matrix.size(), n = matrix[0].size(), sz = m * n;
        vector<bool> visited(sz);
        vector<int> res;
        int dr[] = {0, 1, 0, -1}, dc[] = {1, 0, -1, 0}; // 按右下左上的顺序
        for (int i = 0, r = 0, c = 0, j = 0; i < sz; ++i) {
            if (0 <= r && r < m && 0 <= c && c < n && !visited[r * n + c]) {
                res.push_back(matrix[r][c]);
                visited[r * n + c] = true;
            } else { // 如果越界
                r -= dr[j]; // 回退
                c -= dc[j];
                --i;
                j = (j + 1) % 4; // 换向
            }
            r += dr[j]; // 尝试前进一步
            c += dc[j];
        }
        return res;
    }
};

O(1) space

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return {};
        enum D {N, E, W, S};
        int dx[] = {0, 1, -1, 0}, dy[] = {-1, 0, 0, 1};
        int n = matrix.size(), m = matrix[0].size();
        int size = n * m;
        D d = E;
        vector<int> res;
        for (int i = 0, row = 0, col = 0, t = -1, b = n, l = -1, r = m; i < size; ++i) { // 用tblr来标记当前的上下左右的bound
            res.push_back(matrix[row][col]);
            switch (d) {
                case N: if (row + dy[d] == t) { d = E; ++l; } break;
                case E: if (col + dx[d] == r) { d = S; ++t; } break;
                case W: if (col + dx[d] == l) { d = N; --b; } break;
                case S: if (row + dy[d] == b) { d = W; --r; } break;
                default: break;
            }
            row += dy[d];
            col += dx[d];
        }
        return res;
    }
};