You are starving and you want to eat food as quickly as possible. You want to find the shortest path to arrive at any 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.You can travel to any adjacent cell north, east, south, or west of your current location if there is not an obstacle.
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 = [["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"],["O","O","O","O","O","O","O","O"]] Output: 5
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 200grid[row][col] is '*', 'X', 'O', or '#'.grid contains exactly one '*'.Problem Overview: You are given a grid containing walls (X), empty cells (O), a starting position (*), and food cells (#). From the start, move up, down, left, or right. The goal is to reach any food cell using the minimum number of steps while avoiding walls.
Approach 1: DFS / Backtracking Search (O(m*n) time, O(m*n) space)
A naive idea is to explore every possible path from the starting cell using depth-first search. You recursively move in four directions and track visited cells to avoid cycles. Whenever a food cell is found, record the path length and keep the minimum. While DFS can eventually find the answer, it explores deep paths first and does not naturally guarantee the shortest route. In dense grids this leads to unnecessary exploration, making it inefficient for shortest-path problems on a matrix.
Approach 2: Breadth-First Search (BFS) (O(m*n) time, O(m*n) space)
The grid can be treated as an unweighted graph where each cell connects to up to four neighbors. Breadth-First Search processes nodes level by level, which naturally corresponds to distance in steps. Start from the * cell, push it into a queue, and expand neighbors while marking visited cells. Each BFS layer represents one step from the start. The first time a # cell is reached, the current level count is the shortest path length.
During traversal, skip cells outside bounds, walls (X), or already visited positions. Because each cell is processed at most once, the total work is proportional to the number of cells in the grid. This makes BFS the standard solution for shortest-path problems in an unweighted array-based grid.
Recommended for interviews: Interviewers expect the BFS solution. Shortest path in an unweighted grid is a classic signal for BFS with a queue and level tracking. Mentioning DFS as a brute-force exploration shows problem understanding, but implementing BFS demonstrates strong knowledge of graph traversal patterns commonly tested in interviews.
According to the problem, we need to start from *, find the nearest #, and return the shortest path length.
First, we traverse the entire two-dimensional array to find the position of *, which will be the starting point for BFS, and put it into the queue.
Then, we start BFS, traversing the elements in the queue. Each time we traverse an element, we add the elements in the four directions (up, down, left, and right) of it into the queue, until we encounter #, and return the current layer number.
The time complexity is O(m times n), and the space complexity is O(1). Here, m and n are the number of rows and columns of the two-dimensional array, respectively.
Python
Java
C++
Go
JavaScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS / Backtracking | O(m*n) | O(m*n) | Conceptual brute-force exploration; not ideal for shortest-path guarantees |
| Breadth-First Search (BFS) | O(m*n) | O(m*n) | Best approach for shortest path in an unweighted grid |
| Multi-source BFS Variant | O(m*n) | O(m*n) | Useful when starting from multiple positions or extending the problem |
SHORTEST PATH TO GET FOOD | LEETCODE # 1730 | PYTHON BFS SOLUTION • Cracking FAANG • 3,760 views views
Watch 9 more video solutions →Practice Shortest Path to Get Food with our built-in code editor and test cases.
Practice on FleetCode