package DataStructure.array;

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

/**
 * 54. 螺旋矩阵 https://leetcode.cn/problems/spiral-matrix
 * 题目简述：给定一个m*n的二维数组，从matrix[0][0]开始顺时针螺旋打印数组
 */
public class SpiralOrder {

    public static void main(String[] args) {
        new SpiralOrder().spiralOrder(new int[][]{{7},{9}, {6}});
    }

    /**
     * 思路：要走的圈数为Math.min((m>>1) + m%2, (n>>1) + n%2)，第k圈的圈首即为i = k,j = k，并计算圈长宽
     * 先加入圈首，然后根据长宽顺时针走一圈，注意矩阵宽度大于1才能向左走，矩阵长度大于1才能向上走
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        List<Integer> result = new ArrayList<>(m*n);
        int turnTimes = Math.min((m>>1) + m%2, (n>>1) + n%2); //要走的圈数
        for (int k = 0;k < turnTimes;k++) {
            int i = k, j = k, len = n-2*k, wid = m-2*k;
            result.add(matrix[i][j]);
            //向右
            for (int t = 1;t < len;t++)
                result.add(matrix[i][++j]);
            //向下
            for (int t = 1;t < wid;t++)
                result.add(matrix[++i][j]);
            //向左，矩阵宽度大于1才能向左走
            for (int t = 1;wid > 1 && t < len;t++)
                result.add(matrix[i][--j]);
            //向上，矩阵长度大于1才能向上走
            for (int t = 1;len > 1 && t < wid-1;t++)
                result.add(matrix[--i][j]);
        }
        return result;
    }
}