class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        if (matrix == null || matrix.length == 0) return ans;
        int count = 0;
        int n = matrix.length, m = matrix[0].length;
        boolean[][] visited = new boolean[n][m];
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        int x = 0, y = 0;
        int method = 0;
        while (count < n * m){
            visited[x][y] = true;
            count++;
            ans.add(matrix[x][y]);
            int xx = x + dirs[method][0];
            int yy = y + dirs[method][1];

            while (count < n * m && (xx < 0 || xx >= n || yy < 0 || yy >= m || visited[xx][yy])){
                method = (method + 1) % 4;
                xx = x + dirs[method][0];
                yy = y + dirs[method][1];
            }

            x = xx;
            y = yy;

            //System.out.println(ans.toString() + " x: " + x + " y: " + y);
        }

        return ans;
    }
}