Spiral Matrix

Problem:

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

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

10/4/2018 update
一开始是往右走，如果invalid，就要换方向。所以在一开始就加到结果里面比较合理。
--------------------------------------------------------------------------------------------------------------------------------------------

Analysis:

Since the direction is left -> down -> right -> up. It's intuitive that we come up with direction array. To maintain the boundary we can use a visited[m][n] matrix to help, no need to think about 4 different boundaries. 

本来思路都自己想好了，但是看到要用visited matrix就放弃了。Space is cheap! 这道题实现还挺有挑战的。

Solution：

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix == null || matrix.length == 0 )
            return res;
        int m = matrix.length;
        int n = matrix[0].length;
        
        int[] dx = new int[]{0, 1, 0, -1};
        int[] dy = new int[]{1, 0, -1, 0};
        boolean[][] visited =  new boolean[m][n];
        int x = 0, y = 0;
        int d = 0;
        for (int i = 0; i < m*n; i++) {
             res.add(matrix[x][y]);
             visited[x][y] = true;
            
             int newx = x + dx[d];
             int newy = y + dy[d];
             if (0 <= newx && newx < m && 0 <= newy && newy < n && !visited[newx][newy]) {
                x = newx;
                y = newy;
             } else {
                d = (d + 1) % 4;
                x += dx[d];
                y += dy[d];
             }
        }
        
        return res;
    }
}