package leetcode.array;

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

/**
 * @program: study
 * @description: 螺旋矩阵2
 * @author: 小北丶
 * @create: 2022-02-24 14:53
 **/

public class Spiral_Matrix_II {
    //59. 螺旋矩阵 II 中等
    //给你一个正整数 n ，生成一个包含 1 到 n*n 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

    //版本一 一次for循环模拟
    //dx与dy是个妙笔 定义了数字填充时的判断条件以及到达边界后的偏移量,
    //仔细研究填充过程后就会发现,
    // 向右移动时,x不变,y加一,判断条件为y加一后数组是否越界或者y加一的位置已经填充了数字
    // 向下移动时,x加一,y不变,判断条件为x加一后数组是否越界或者x加一的位置已经填充了数字
    // 向走移动时,x不变,y减一,判断条件为y减一后数组是否越界或者y减一的位置已经填充了数字
    // 向上移动时,x减一,y不变,判断条件为x减一后数组是否越界或者x减一的位置已经填充了数字
    // 由以上x,y的变化与判断条件一致所以设计dx与dy 每次赋值后,判断当前位置加上偏移量后是否还合法,不合法则改变偏移量,即改变方向
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        int[] dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};  //方向偏移数组
        int x = 0, y = 0;  //当前位置
        for (int i = 1, d = 0; i <= n * n; i++) {
            res[x][y] = i;
            int a = x + dx[d], b = y + dy[d];
            if (a < 0 || a == n || b < 0 || b == n || res[a][b] != 0) {  //出界或者该位置已经被走过
                d = (d + 1) % 4;   //更改方向
                a = x + dx[d];
                b = y + dy[d];  //下一个要走的位置
            }
            x = a;
            y = b;
        }
        return res;
    }
    //版本2 外旋改为内旋,如果外旋该内旋的话一要控制转的圈数,二要控制每一圈转多大,三要控制方向的变化,这样就违背了简化的初衷所以放弃


    //版本3 纯模拟解法  以下解法仅适用于n*n矩阵,当使用m*n矩阵时会出现大量bug
    public int[][] generateMatrix3(int n) {
        int[][] arr = new int[n][n];
        int c = 1, j = 0;
        while (c <= n * n) {
            for (int i = j; i < n - j; i++)
                arr[j][i] = c++;
            for (int i = j + 1; i < n - j; i++)
                arr[i][n - j - 1] = c++;
            for (int i = n - j - 2; i >= j; i--)
                arr[n - j - 1][i] = c++;
            for (int i = n - j - 2; i > j; i--)
                arr[i][j] = c++;
            j++;
        }
        return arr;
    }


    //54 螺旋矩阵  中等
    //给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
    //设定四个边界
    public List<Integer> spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return new LinkedList<>();
        int l = 0;
        int r = matrix[0].length - 1;
        int u = 0;
        int d = matrix.length - 1;
        List<Integer> list = new LinkedList<>();
        while (l <= r && u <= d){
            for (int i = l; i <= r; i++) {
                list.add(matrix[u][i]);
            }
            u++;
            for (int i = u; i <= d; i++) {
                list.add(matrix[i][r]);
            }
            r--;
            for (int i = r; i >= l && u <= d; i--) {
                list.add(matrix[d][i]);
            }
            d--;
            for (int i = d; i >= u && l <= r; i--) {
                list.add(matrix[i][l]);
            }
            l++;
        }
        return list;
    }

}