# 【LeetCode】 59. Spiral Matrix II

## Description
> Given a positive integer n, generate a square matrix filled with elements from 1 to n^2 in spiral order.

> 給一個正整數n，請產生一個方陣，照螺旋的順序填入1到n^2。

## Example:

Example:

Input: 3
Output:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

## Solution

* 用一個變數`i`去紀錄現在產生到哪裡。
* 用變數`x`和`y`去紀錄現在的位置。
* 用變數`dir`去控制下一次的位置。
* 演算法分成三步驟：
* 填入矩陣
* 更新方向
* 更新位置
* 填入矩陣後判斷是否完成。
* 更新方向需要先判斷下一步是否合法，如果不合法才改變方向，否則就照原方向繼續走。

### Code

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n,vector<int>(n,0));
        
        int x=0,y=0;
        int dir=0;
        for(int i=1;;i++)
        {
            //set
            ans[y][x]=i;
            if(i==n*n)
                break;
            //control dir
            while(1)
            {
                if(dir%4==0)
                {
                    if(x!=n-1 && ans[y][x+1]==0)
                        break;
                }
                else if(dir%4==1)
                {
                    if(y!=n-1 && ans[y+1][x]==0)
                        break;
                }
                else if(dir%4==2)
                {
                    if(x!=0 && ans[y][x-1]==0)
                        break;
                }
                else
                {
                    if(y!=0 && ans[y-1][x]==0)
                        break;
                }
                dir++;
            }
            
            //move
            if(dir%4==0)
            {
                x++;
            }
            else if(dir%4==1)
            {
                y++;
            }
            else if(dir%4==2)
            {
                x--;
            }
            else
            {
                y--;
            }
        }
        
        return ans;
    }
};

###### tags: `LeetCode` `C++`