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].



如果按照直接的思路去做，估计会有一大堆恶心的if、else来判断边界条件，所以用一个变形的dfs来做，每次标记一个dfs的方向，先按照这个方向去找，如果找到头，再找下一个方向。

比如根据题目要求，向右查找的后继方向应该是向下，像左查找的后继方向应该是向上等等。


public class Solution {
    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if(matrix==null||matrix.length==0||matrix[0].length==0){
            return result;
        }
        boolean [][]flags = new boolean[matrix.length][matrix[0].length];
        dfs(matrix,flags,result,0,0,1);
        return result;
    }
      
    public void dfs(int[][] matrix, boolean [][] flags, ArrayList<Integer> result, int i, int j, int direction){
        if(i<0||j<0||i>=matrix.length||j>=matrix[0].length||flags[i][j]){
            return;
        }
        result.add(matrix[i][j]);
        flags[i][j] = true;
          
        switch(direction){
            case 1://right
                dfs(matrix,flags,result,i,j+1,1);
                dfs(matrix,flags,result,i+1,j,2);
                break;
            case 2://down
                dfs(matrix,flags,result,i+1,j,2);
                dfs(matrix,flags,result,i,j-1,3);
                break;
            case 3: // left
                dfs(matrix,flags,result,i,j-1,3);
                dfs(matrix,flags,result,i-1,j,4);
                break;
            case 4:
                dfs(matrix,flags,result,i-1,j,4);
                dfs(matrix,flags,result,i,j+1,1);
                break;
                              
        }
    }
}