# 向左移动
i,j=t,l
while j<=r and head:
    ls[i][j]=head.val
    head=head.next
    j+=1
t+=1
i,j=t,r
# 向下走
while i<=d and head:
    ls[i][j]=head.val
    head=head.next
    i+=1
r-=1
i,j=d,r
while j>=l and head:
    ls[i][j]=head.val
    head=head.next
    j-=1
d-=1
i,j=d,l
while i>=t and head:
    ls[i][j]=head.val
    head=head.next
    i-=1
l+=1

ans=[[-1]*n for _ in range(m)]
# 模拟右下左上
d=[[0,1],[1,0],[0,-1],[-1,0]]
idx=0
cur=[0,0]
while head:
    l,r=cur
    ans[l][r]=head.val
    i,j=d[idx]
    if not 0<=l+i<m or not 0<=r+j<n or  ans[l+i][r+j]!=-1:
        idx=(idx+1)%4
        i,j=d[idx]
    cur=[l+i,r+j]
    head=head.next

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m,n=len(matrix),len(matrix[0])
        ls=[(0,1),(1,0),(0,-1),(-1,0)]
        sz=m*n
        vis=[[1]*n for _ in range(m)]
        ans=[0]*sz
        cnt=[0,0]
        idx=0
        ls_id=0
        while idx<sz:
            l,r=cnt
            ans[idx]=matrix[l][r]
            vis[l][r]=0
            i,j=ls[ls_id]
            if not 0<=l+i<m or not 0<=r+j<n or vis[l+i][r+j]==0:
                ls_id=(ls_id+1)%4
                i,j=ls[ls_id]
            cnt=[l+i,r+j]
            idx+=1
        return ans

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        ls=[(0,1),(1,0),(0,-1),(-1,0)]
        sz=n*n
        vis=[[1]*n for _ in range(n)]
        ans=[[1]*n for _ in range(n)]
        cnt=[0,0]
        idx=0
        ls_id=0
        while idx<sz:
            l,r=cnt
            ans[l][r]=idx+1
            vis[l][r]=0
            i,j=ls[ls_id]
            if not 0<=l+i<n or not 0<=r+j<n or vis[l+i][r+j]==0:
                ls_id=(ls_id+1)%4
                i,j=ls[ls_id]
            cnt=[l+i,r+j]
            idx+=1
        return ans

class Solution:
    def spiralMatrixIII(self, rows: int, cols: int, rs: int, cs: int) -> List[List[int]]:
        d=[[0,1],[1,0],[0,-1],[-1,0]]
        idx=0
        a,b=rs,cs
        ans=[[a,b]]
        step=0
        while len(ans)<rows*cols:
            i,j=d[idx]
            step+=1
            for i in range(2):
                for j in range(step):
                    l,r=d[idx]
                    a+=l
                    b+=r
                    if 0<=a<rows and 0<=b<cols:
                        ans.append([a,b])
                idx=(idx+1)%4
        return ans

class Solution:
    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:
        ans=[[-1]*n for _ in range(m)]
        # 模拟右下左上
        d=[[0,1],[1,0],[0,-1],[-1,0]]
        idx=0
        cur=[0,0]
        while head:
            l,r=cur
            ans[l][r]=head.val
            i,j=d[idx]
            if not 0<=l+i<m or not 0<=r+j<n or  ans[l+i][r+j]!=-1:
                idx=(idx+1)%4
                i,j=d[idx]
            cur=[l+i,r+j]
            head=head.next
        return ans