Problem statement

https://leetcode.com/problems/shortest-path-to-get-food/

Solution

Very classical bfs problem, where we need to find the shortest distance.

Complexity

Time complexity is O(n*m), space complexity as well.

Code

class Solution:
    def getFood(self, grid):
        m, n = len(grid), len(grid[0])
        for x, y in product(range(m), range(n)):
            if grid[x][y] == "*": 
                queue = deque([(0, x, y)])
                    
        v = set()
                      
        while queue:
            dist, x, y = queue.popleft()
            if grid[x][y] == "#": return dist
            for dx, dy in (1, 0), (-1, 0), (0, -1), (0, 1):
                if 0 <= x+dx < m and 0 <= y+dy < n and grid[x+dx][y+dy] in "#O" and (x + dx, y + dy) not in v:
                    v.add((x+dx, y+dy))
                    queue.append((dist + 1, x + dx, y + dy))
                    
        return -1