Leetcode - 1730. Shortest Path To Get Food

Medium

Jan 13, 2026

#graph

#bfs

1730. Shortest Path To Get Food

You are starving and you want to eat food as quickly as possible. You want to find the shortest path to arrive at a food cell.

You are given an m x n character matrix, grid, of these different types of cells:

'*' 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.

Return the length of the shortest path for you to reach any food cell. If there is no path for you to reach food, return -1.

Example 1:

Input: grid = [["X","X","X","X","X","X"],["X","*","O","O","O","X"],["X","O","O","#","O","X"],["X","X","X","X","X","X"]]
Output: 3
Explanation: It takes 3 steps to reach the food.

Example 2:

Input: grid = [["X","X","X","X","X"],["X","*","X","O","X"],["X","O","X","#","X"],["X","X","X","X","X"]]
Output: -1
Explanation: It is not possible to reach the food.

Example 3:

Input: grid = [["X","X","X","X","X","X","X","X"],["X","*","O","X","O","#","O","X"],["X","O","O","X","O","O","X","X"],["X","O","O","O","O","#","O","X"],["X","X","X","X","X","X","X","X"]]
Output: 6
Explanation: There can be multiple food cells. It only takes 6 steps to reach the bottom food.

Example 4:

Input: grid = [["O","*"],["#","O"]]
Output: 2

Example 5:

Input: grid = [["X","*"],["#","X"]]
Output: -1

Notes

Intuition

Finding the shortest path in an unweighted grid is a classic BFS problem. BFS explores all cells at distance k before any cell at distance k+1, guaranteeing the first food cell reached is the closest.

Implementation

First, locate the starting position (*). Initialize a queue with the start coordinate and path length 0, plus a visited set. Process cells level by level: for each cell, check its four neighbors. Skip if visited or blocked (X). If it's food (#), return the current path length + 1. Otherwise, add to visited and queue with incremented path.

Edge-cases

If BFS completes without finding food, return -1 (no reachable food). The visited set prevents revisiting cells and infinite loops.

Time: O(m * n) — each cell visited at most once
Space: O(m * n) — visited set and queue

Complexity

Solution

from typing import List, Tuple
from collections import deque

class Solution:
    def neighbours(self, coord: Tuple[int, int], grid: List[List[str]]) -> List[Tuple[int, int]]:
        dirs = [(0, 1), (0, -1), (-1, 0), (1, 0)]
        result = []
        i, j = coord
        for di, dj in dirs:
            ni, nj = i + di, j + dj
            if ni < 0 or ni >= len(grid) or nj < 0 or nj >= len(grid[0]):
                continue
            result.append((ni, nj))
        return result
    def shortestPath(self, grid: List[List[str]]) -> int:
        # Step 1: Find start coordinate
        start = (-1, -1)
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] == "*":
                    start = (i, j)
                    break

        # Step 2: BFS to find shortest path with visited set
        visited = set([start])
        q = deque([(start, 0)])
        while q:
            curr, path = q.popleft()
            for n in self.neighbours(curr, grid):
                ni, nj = n
                if n in visited or grid[ni][nj] == "X":
                    continue
                if grid[ni][nj] == "#":
                    return path + 1
                visited.add(n)
                q.append((n, path + 1))
        return -1

if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()