from typing import List


class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        visit_dir = 0  # 0=right 1=down 2=left 3=up
        boundary_hor = [0, len(matrix[0]) - 1]
        boundary_vert = [0, len(matrix) - 1]

        rlt = []
        i = j = 0
        while boundary_vert[0] <= i <= boundary_vert[1] \
                and boundary_hor[0] <= j <= boundary_hor[1]:
            rlt.append(matrix[i][j])
            if visit_dir == 0:
                if j >= boundary_hor[1]:  # 改变方向
                    i += 1
                    visit_dir = (visit_dir + 1) % 4
                    boundary_vert[0] += 1
                else:
                    j += 1
            elif visit_dir == 1:
                if i >= boundary_vert[1]:  # 改变方向
                    j -= 1
                    visit_dir = (visit_dir + 1) % 4
                    boundary_hor[1] -= 1
                else:
                    i += 1
            elif visit_dir == 2:
                if j <= boundary_hor[0]:  # 改变方向
                    i -= 1
                    visit_dir = (visit_dir + 1) % 4
                    boundary_vert[1] -= 1
                else:
                    j -= 1
            elif visit_dir == 3:
                if i <= boundary_vert[0]:  # 改变方向
                    j += 1
                    visit_dir = (visit_dir + 1) % 4
                    boundary_hor[0] += 1
                else:
                    i -= 1

        return rlt


sol = Solution()
rlt = sol.spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
print(rlt)
rlt = sol.spiralOrder([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]])
print(rlt)
