Spiral Matrix

题目
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

答案

class Solution {
    private boolean valid(int[][] matrix, boolean[][] visited, int x, int y) {
        return x >= 0 && x < matrix.length && y>= 0 && y < matrix[0].length && visited[x][y] == false;
    }
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        if(matrix.length == 0) return list;
        int m = matrix.length, n = matrix[0].length;
        boolean[][] visited = new boolean[m][n];
        int[][] dxdy = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        
        
        // go right, down, left, top. Change directions when hit a visited position
        int x = 0, y = -1, tx = 0, ty = 0;
        int cnt = 0, dir = 0;
        while(cnt < m * n) {
            tx = x + dxdy[dir][0];
            ty = y + dxdy[dir][1];

            if(valid(matrix, visited, tx, ty)) {
                x = tx;
                y = ty;
            }
            else {
                dir = (dir + 1) % 4;
                continue;
            }

            list.add(matrix[x][y]);
            visited[x][y] = true;
            cnt++;
        }
        return list;
    }
}