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

/**
 * 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].
 二维数组的螺旋取数，思路和翻转二维数组差不多，分层然后每层取数
 难点是判断层数是根据短边确定，每层取数时上下左右四行（列）的坐标确定，注意长和宽（m和n）分清楚
 还有一个难点是如果短边是一个奇数，那么最后一层（即层数是短边/2（层数从0开始）时）是取不到的，要单独去判断，
 分情况（最后一行是竖着还是横着）进行取数。
 写代码时出错的地方：
 1.判断层数一开始用长边计算的
 2.忘了考虑输入是空数组的情况
 3.没考虑短边是奇数时，最后一层取不到
 二维数组分层，每条边的坐标(顺时针取)可以记住：
 i为层数，j为每层的循环数,m是行数，n是列数
 上边：（i,i+j）
 右边：（i+j,n-1-i）
 下边：（m-1-i,n-1-i-j）
 左边：（n-1-i-j,i）
 */
public class Q54SpiralMatrix {
    public static void main(String[] args) {
        int[][] matrix = new int[][]{{1,2,3},{4,5,6},{7,8,9}};
        System.out.println(spiralOrder(matrix));
    }
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int m = matrix.length;
        if(m == 0)
            return res;
        int n = matrix[0].length;
        int l = Math.min(m,n);
        int k = l/2;
        for(int i = 0;i < k;i++)
        {
            for (int j = 0; j < n-(i*2)-1; j++) {
                res.add(matrix[i][i+j]);
            }
            for (int j = 0; j < m-(i*2)-1; j++) {
                res.add(matrix[i+j][n-1-i]);
            }
            for (int j = 0; j < n-(i*2)-1; j++) {
                res.add(matrix[m-1-i][n-1-i-j]);
            }
            for (int j = 0; j < m-(i*2)-1; j++) {
                res.add(matrix[m-1-i-j][i]);
            }
        }
        if (l%2 != 0)
        {
            if (l == m)
            {
                for (int j = 0; j <= n-(k*2)-1; j++) {
                    res.add(matrix[k][k+j]);
                }
            }
            else
            {
                for (int j = 0; j <= m-(k*2)-1; j++) {
                    res.add(matrix[k+j][n-1-k]);
                }
            }
        }
        return res;
    }
}