> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Shortest Path to Get Food Python Solution

> Tested Python solution for LeetCode 1730 with 19 pytest cases. Generate a practice environment with lcpy.

LeetCode 1730, Medium. Topics: Array, Breadth-First Search, Matrix. [View on LeetCode](https://leetcode.com/problems/shortest-path-to-get-food/description/).

Generate this problem as a practice environment: tested reference solution, 19 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1730   # by problem number
lcpy gen -s shortest_path_to_get_food   # by problem name
```

## Problem

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`.

### Examples

```
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.
```

```
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.
```

```
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.
```

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

### Constraints

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 200`
* `grid[row][col]` is `'*'`, `'X'`, `'O'`, or `'#'`.
* The `grid` contains exactly one `'*'`.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/shortest_path_to_get_food/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/shortest_path_to_get_food/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import deque


class Solution:
    # Time: O(m * n)
    # Space: O(m * n)
    def get_food(self, grid: list[list[str]]) -> int:
        rows, cols = len(grid), len(grid[0])

        start = next((r, c) for r in range(rows) for c in range(cols) if grid[r][c] == "*")

        queue: deque[tuple[tuple[int, int], int]] = deque([(start, 0)])
        visited = {start}

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        while queue:
            (r, c), steps = queue.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:
                    if grid[nr][nc] == "#":
                        return steps + 1
                    if grid[nr][nc] == "O":
                        visited.add((nr, nc))
                        queue.append(((nr, nc), steps + 1))

        return -1
```

## Complexity

| Time      | Space     |
| --------- | --------- |
| O(m \* n) | O(m \* n) |

## Tags

[Grind](/catalog/grind).