# 1730. Shortest Path to Get Food

###### tags: `leetcode` `bfs` `1730` `medium` `rewrite`

## :memo: Question

## :memo: 題意

* '*' is your location. There is exactly one '*' cell.
* '#' is a food cell. There may be multiple food cells.
* 'O' is free space, and you can travel through these cells.
* 'X' is an obstacle, and you cannot travel through these cells.

:bulb: 給你一個 m * n 的矩陣，求你到食物的那個點的最短距離。

## :memo: leetcode solution
* :medal: **思考一**: 像這種的找最短距離的就是 bfs，請牢牢地印在你腦袋裡。

# pseudo code
# 1. traverse all location in the matrix to find your location
# 2. if you find the your location，start to use queue to implement bfs algo
# 3. prepare a visited matrix
# 4. if you start at (x,y) and the next step is to find the four position to find 
# food => (x+1,y) (x-1,y) (x,y+1) (x,y-1)
# 5. if the next location != 'X' and not visited and (new_x,new_y) didn't out of range , append the location to the queue
# 6. if queue pop value == '#' and return d

class Solution:
    def getFood(self, grid: List[List[str]]) -> int:
        
        def bfs(i,j,grid,matrix):
            matrix[i][j] = 1
            queue = deque([[i,j,0]])
            
            while queue:
                x,y,d = queue.popleft()
                if grid[x][y] == '#': return d
                for new_x, new_y in [[x+1,y],[x,y+1],[x-1,y],[x,y-1]]:
                    if 0 <= new_x < m and 0 <= new_y < n: 
                        if grid[new_x][new_y] != 'X' and not matrix[new_x][new_y]:
                            matrix[new_x][new_y] = 1
                            queue.append([new_x, new_y, d+1])
                            
        m = len(grid)
        n = len(grid[0])
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '*':
                    ans = bfs(i,j,grid, [[0] * n for i in range(m)]) 
                    return ans if ans else -1

## :memo: bigO
* 時間複雜度: O(m* n)
* 空間複雜度: O(2 * m * n)