1730. Shortest Path to Get Food

class Solution:
    def getFood(self, grid: List[List[str]]) -> int:
        """ tc O(R*C) sc O(R*C)
        main idea: BFS 
        1. find start point, put its position into queue 
        2. expand from four directions (1) check if neighbour position is valid O, push onto queue (2) if neighour is target location, return final res 
        3. each step determined to go next level, need to mark that position unreachable to avoid repeated visit.  
        """
        q = collections.deque()
        r,c = len(grid),len(grid[0])
        for i in range(r):
            for j in range(c):
                if grid[i][j] == '*':
                    q.append([0,(i,j)])
                    break
        
        dirs = [(0,1),(1,0),(0,-1),(-1,0)]
        while q:
            level, pos = q.popleft()
            for dx,dy in dirs:
                nx = dx + pos[0]
                ny = dy + pos[1]
                if 0<= nx <r and 0<= ny < c:
                    if grid[nx][ny] == 'O':
                        grid[nx][ny] = 'X' # avoid dead circle 
                        q.append([level+1,(nx,ny)])
                    elif grid[nx][ny] == '#':
                        return level + 1 
        return -1