# 59. Spiral Matrix II
https://leetcode.com/problems/spiral-matrix-ii/description/
###### tags: `Python`,`Leetcode`
## Code

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        mat = [[0] * n for i in range(n)]

        def dfs(r,c):
            global start
            if r  >= n or r < 0 or c >= n or c < 0 or mat[r][c] != 0: 
                return
            
            mat[r][c] = start
            start += 1
            
            if c+1 >= r:
                dfs(r,c+1)
            dfs(r+1,c)
            dfs(r,c-1)
            dfs(r-1,c)
        global start
        start = 1
        dfs(0,0)
        return mat

## 題意
* 題目會給一個 `n` ，接著我們要依螺旋順序把數字 `1` ～ `n*n` 放進大小為 `n*n` 的矩陣中
* **Example**：

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

## 思路
* 這種走到底就轉彎的路徑讓我想到 DFS ，就用 DFS 做看看
* 但這種做法其實 Runtime 表現上不是上佳，大家參考看看就好
## 解法

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        mat = [[0] * n for i in range(n)]
# 表達式 A = [[0] * n for _ in range(n)] 會創建一個大小為 n x n 的二維列表，其中每個元素都是 0
# 表達式 A = [[0] * n] * n 則會創建一個大小為 n x n 的二維列表，其中每一行都是指向同一個列表對象的引用(指到同一塊記憶體) 。這意味著如果修改其中一行的元素，其他行的相應元素也會被修改
        def dfs(r,c):
            global start
            # 全局變量 start 記錄當前填充的元素值
            if r  >= n or r < 0 or c >= n or c < 0 or mat[r][c] != 0: 
            # 如果搜索到邊界，或者當前位置已經被填充，則返回
            # 這個 mat[r][c] != 0 條件要放在最後，因為若超過邊界（r,c > n），會導致 out of index
                return
        
            mat[r][c] = start
            # 走到的那一格填入數字
            start += 1
            # 下一個數字 = 現在的數字 ＋ 1
            
            if c+1 >= r:# 如果沒有這個判斷式，往右往下往上走後發現往右還有路走 ➡️ 沒辦法乖乖往上走到底
                # c + 1 >= r 算是一個歸納出來的結果
                dfs(r,c+1) # 往右走
            dfs(r+1,c) # 往下走
            dfs(r,c-1) # 往左走
            dfs(r-1,c) # 往上走
        global start
        start = 1
        # 定義全局變量 start，並初始化為 1
        dfs(0,0)
        return mat

## 解法 2
* 問了一下 ChatGPT，請他使用 DFS 解這題，出現了一個我覺得蠻可愛的解法，提供給大家參考
* Runtime 還不錯，就是有點耗記憶體

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        mat = [[0] * n for _ in range(n)]
        num = 1
        def dfs(r, c, direction):
            nonlocal num
            if num > n * n:
                return
            if mat[r][c] == 0:
                mat[r][c] = num
                num += 1
            if direction == 0: # 向右
                if c < n - 1 and mat[r][c + 1] == 0:
                    dfs(r, c + 1, 0)
                else:
                    dfs(r + 1, c, 1)
            elif direction == 1: # 向下
                if r < n - 1 and mat[r + 1][c] == 0:
                    dfs(r + 1, c, 1)
                else:
                    dfs(r, c - 1, 2)
            elif direction == 2: # 向左
                if c > 0 and mat[r][c - 1] == 0:
                    dfs(r, c - 1, 2)
                else:
                    dfs(r - 1, c, 3)
            else: # 向上
                if r > 0 and mat[r - 1][c] == 0:
                    dfs(r - 1, c, 3)
                else:
                    dfs(r, c + 1, 0)
        dfs(0, 0, 0)
        return mat