#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型vector<vector<>> 
     * @return int整型vector
     */
    vector<int> spiralOrder(vector<vector<int> >& matrix) {
        // write code here
        int m = matrix.size(), n = matrix[0].size();
        //先设定右下左上的顺时针方向
        vector<vector<int>> d{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        //记录走过的元素
        vector<bool> vis(m * n, false);
        // x, y初始化坐标原点,cnt:元素个数总和, f:当前遍历的方向
        int x = 0, y = 0, cnt = 0, f = 0;
        //元素总数
        int all = m * n;
        vector<int> ans;
        while(cnt++ < all){
            ans.push_back(matrix[x][y]);
            vis[x * n + y] = true;
            int nx = x + d[f][0], ny = y + d[f][1];
            //如果下个元素不在矩阵中,或者已经遍历过,则变换方向
            if(nx < 0 || nx >= m || ny < 0 || ny >= n || vis[nx * n + ny]){
                f = (f + 1) % 4;
                nx = x + d[f][0];
                ny = y + d[f][1];
            }
            x = nx;
            y = ny;
        }
        return ans;
    }
};