# 2326. Spiral Matrix IV
###### tags: `spiral`


best spiral iteration: https://hackmd.io/OG9adSnmRPycEPFh0ST6aQ

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:
        def out_of_index(i,j):
            return not (0<=i<m and 0<=j<n)
            
        seen = set()
        i,j=0,0
        directions=[(0,1),(1,0),(0,-1),(-1,0)]
        cur_d = 0  # current direction
        spiral=[]
        while (i,j) not in seen and len(spiral)<m*n:
            seen.add((i,j))
            spiral.append((i,j))
            
            di,dj=directions[cur_d] # try not, if bad, change direction
            if out_of_index(i+di,j+dj) or (i+di,j+dj) in seen:
                cur_d += 1
                cur_d = cur_d % 4
            di,dj=directions[cur_d]
            i,j = i+di,j+dj  # just use new direction to go to next, let next loop check
            
        grid = [ [-1]*n for _ in range(m)]
        
        li = []
        node = head
        while node:
            li.append(node.val)
            node = node.next
            
        for val, (i,j) in zip(li, spiral):
            grid[i][j]=val
        return grid