# 【LeetCode】59. Spiral Matrix II

## Question link
[Link](https://leetcode.com/problems/spiral-matrix-ii/description/)
## Intuition
> Given a positive integer `n`, generate an `n x n` `matrix` filled with elements from `1` to `n2` in spiral order.
給定一個整路`n`，以迴旋方式產生一個陣列，並將數字從`1`填充到`n2`
題目要求以迴旋方式將數字填入到矩陣中，因此我們需要考慮**每一個邊**，該如何設計迴圈的操作條件，依舊是要堅持**迴圈不變量**的原則，填充的順序為

* 上列為由左到右
* 右列為由上至下
* 下列為由右至左
* 左列為由下至上

首先決定這樣的操作會循環幾次，如果`n`是奇數則只要做`n / 2`次，中間元素最後處理就好，如果是偶數次也是做`n / 2`次。
接著設計起始位置與終止位置，作為4個邊循環的條件，每次繞完後將起始位置加一，終止位置減一，代表著向內部進行縮圈，在這次實作中保持左必右開的循環原則

## Approach

1. 宣告`loop`變數作為每繞外圈的次數
2. 宣告`start_x`與`start_y`作為起始位置的索引
3. 宣告`end_x`與`end_y`作為終止位置
4. 宣告`count`作為元素計數
5. 循環開始
1. 在`start_x`固定，沿著`y`軸循環元素
2. 在`end_y`固定，沿著`x`軸循環元素
3. 在`end_x`固定，反方向沿著`y`軸循環元素
4. 在`start_y`固定，沿著x軸循環元素
6. 最後處理中間元素

## Complexity
- Time complexity: $O(n^2)$
- Space complexity: $O(1)$
## Code

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n, vector<int>(n, 0));
        int loop = n / 2;
        int start_x = 0;
        int start_y = 0;
        int end_x = n - 1;
        int end_y = n - 1;
        int count = 1;
        while(loop) {
            for (int i = start_x; i < end_x; i++){
                ans[start_y][i] = count++; 
            }
            for (int i = start_y; i < end_y; i++){
                ans[i][end_x] = count++;
            }
            for (int i = end_x; i > start_x; i--){
                ans[end_y][i] = count++;
            }
            for (int i = end_y; i > start_y; i--){
                ans[i][start_x] = count++;
            }
            start_x++;
            start_y++;
            end_x--;
            end_y--;
            loop--;
        }
        if (n % 2 == 1){
            ans[n / 2][n / 2] = count;
        }
        return ans;
    }
};