import java.util.ArrayList;
import java.util.List;

public class _54 {
    static class Solution{
        public List<Integer> spiralOrder(int[][] matrix) {
            //方向 [0,1] ->[1,0] ->[0,-1] ->[-1,0]
            // 碰到边缘或碰到访问过的，调整方向
            int M = matrix.length;
            int N = matrix[0].length;
            boolean[][] v = new boolean[M][N];
            List<Integer> res = new ArrayList<>();
            int[] dirs = {0,1,0,-1,0};
            int cur = 0;
            int i = 0,j = 0;
            while(res.size() < M*N){
                if(i < 0 || i >= M || j < 0 || j >=N || v[i][j]){
                    i -= dirs[cur];
                    j -= dirs[cur+1];
                    cur = (cur + 1) % 4;
                }else{
                    res.add(matrix[i][j]);
                    v[i][j] = true;
                }
                i += dirs[cur];
                j += dirs[cur+1];
            }
            return res;
        }
    }
}