###### tags: `Leetcode` `medium` `array` `python`

# 59. Spiral Matrix II

## [題目連結:] https://leetcode.com/problems/spiral-matrix-ii/

## 題目:
Given a positive integer ```n```, generate an ```n x n matrix``` filled with elements from ```1``` to ```n**2``` in spiral order.

**Example 2:**

Input: n = 1
Output: [[1]]

#### [圖片來源:]https://leetcode.com/problems/spiral-matrix-ii/

## 解題想法:
* 題目要求輸入n，產生n * n 的matrix，且內容要由左上1 ~ n * n，順時鐘產生
* 解題思考:
* 不能按照xy座標去想 要按照code矩陣呈現
* 先向右(同列，不同行)->向下(不同列，同行)->向左->向上..重複
* direction = [[0,1],[1,0],[0,-1],[-1,0]]
* dir[0] 往右(0,1)
* dir[1] 往下(1,0)
* dir[2] 往左(0,-1)
* dir[3] 往上(-1,0)
* 變換方向條件:走到邊界or碰到已填過
* (n+1)%4
* 透過cur_dir依序選擇當前0~3方向

## Python:

class Solution(object):
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        dirs=[[0,1],[1,0],[0,-1],[-1,0]]
        #初始在(0,0)格中 方向為右
        curX=0
        curY=0
        curD=0 
        res=[[0 for _ in range(n)] for _ in range(n)]
        #填數
        for i in range(1,n*n+1):
            res[curX][curY]=i
            #計算下個位置
            nextX=curX+dirs[curD][0]
            nextY=curY+dirs[curD][1]
            #判斷是否出界or已經填過:
            if nextX<0 or nextX>n-1 or nextY<0 or nextY>n-1 or res[nextX][nextY]!=0:
                curD=(curD+1)%4 #更改方向
            #安全走到下個位置
            curX+=dirs[curD][0]
            curY+=dirs[curD][1]
        return res
        
if __name__ == '__main__':
    result = Solution()
    ans = result.generateMatrix(n=3)
    print(ans)
#Input: n = 3
#Output: [[1,2,3],[8,9,4],[7,6,5]]