/**
1. 根据题意模拟整个过程, 我们发现是按右下左上这样方向去遍历, 每次碰到边界或已经访问过的数就改变方向
2. 记4个方向dir分别为0, 1, 2, 3, 每次走时探测下一个位置是不是要转向, 如果要的转向的话 dir++, 直到3个方向都不能走为止(不能回走)
*/

class Solution {
    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        if (matrix == null || matrix.length == 0) return list;

        int x = 0, y = 0, dir = 0, finish = 0;
        boolean[][] visit = new boolean[matrix.length][matrix[0].length];
        while (finish < 3){
            int nx = x + dx[dir], ny = y + dy[dir];
            if (!isVaildIndex(nx, ny, visit)) {
                dir = (dir + 1) % 4;
                finish ++;
                continue;
            }
            finish = 0;
            visit[x][y] = true;
            list.add(matrix[x][y]);
            x = nx;
            y = ny;
        }
        list.add(matrix[x][y]);
        return list;
    }

    public boolean isVaildIndex(int x, int y, boolean[][] visit){
        return 0 <= x && x < visit.length && 0 <= y && y < visit[0].length && !visit[x][y];
    }
}