class Solution {
public:
    vector<pair<int, int>> moves {
        {  0, +1 }, // right
        { +1,  0 }, // down
        {  0, -1 }, // left
        { -1,  0 }, // up
    };
    vector<vector<bool>> visited;

    bool valid(int x, int y)
    {
        return 0 <= x && x < visited.size() &&
               0 <= y && y < visited[0].size();
    }

    void walk(int x, int y, vector<vector<int>>& matrix, vector<int>& ans, int direction = 0)
    {
        visited[x][y] = true;
        ans.push_back(matrix[x][y]);
        int n = moves.size();
        for (int i = 0; i < n; ++i)
        {
            int dx, dy, nextDirection = (direction + i) % n;
            tie(dx, dy) = moves[nextDirection];
            if (!valid(x + dx, y + dy) || visited[x + dx][y + dy])
            {
                continue;
            }
            walk(x + dx, y + dy, matrix, ans, nextDirection);
        }
    }

    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.empty()) { return {}; }

        vector<int> ans;
        visited.resize(matrix.size(), vector<bool>(matrix[0].size(), false));
        walk(0, 0, matrix, ans);
        return ans;
    }
};