from typing import List

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        tar = m * n
        visit = set()
        res = []
        x, y = 0, -1
        dx, dy = 0, 1
        for num in range(tar):
            x, y = x + dx, y + dy
            res.append(matrix[x][y])
            visit.add((x, y))
            dx, dy = self.coor((x, y), (dx, dy), visit, m, n)
        return res


    def coor(self, coord, direct, visit, m, 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 == m - 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)

if __name__ == "__main__":
    s = Solution()
    a = s.spiralOrder([[1,2,3,4],[5,6,7,8],[9,10,11,12]])

    print(a)