from typing import List

# def generateMatrix(n: int) -> List[List[int]]:
    # 法一
    # l, r, t, b = 0, n - 1, 0, n - 1
    # res = [[0 for _ in range(n)] for _ in range(n)]
    # num, tar = 1, n * n
    # while num <= tar:
    #     for i in range(l, r + 1):  # left to right
    #         res[t][i] = num
    #         num += 1
    #     t += 1
    #     for i in range(t, b + 1):  # top to bottom
    #         res[i][r] = num
    #         num += 1
    #     r -= 1
    #     for i in range(r, l - 1, -1):  # right to left
    #         res[b][i] = num
    #         num += 1
    #     b -= 1
    #     for i in range(b, t - 1, -1):  # bottom to top
    #         res[i][l] = num
    #         num += 1
    #     l += 1
    # return res

# 法二
class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        tar = n * n
        visit = set()
        x, y = 0, -1
        dx, dy = 0, 1
        res = [[0 for _ in range(n)] for _ in range(n)]
        for num in range(tar):
            x, y = x + dx, y + dy
            visit.add((x, y))
            res[x][y] = num + 1
            dx, dy = self.coor((x, y), (dx, dy), visit, n)
        return res


    def coor(self, coord, direct, visit, n):
        x, y = coord
        dx, dy = direct
        if dx == 0 and dy == 1:
            if y == n - 1 or (x, y + 1) in visit:
                return (1, 0)
        if dx == 1 and dy == 0:
            if x == n - 1 or (x + 1, y) in visit:
                return (0, -1)
        if dx == 0 and dy == -1:
            if y == 0 or (x, y - 1) in visit:
                return (-1, 0)
        if dx == -1 and dy == 0:
            if (x - 1, y) in visit:
                return (0, 1)
        return (dx, dy)