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 thelength of the shortest path for you to reach any food cell. If there is no path for you to reach food, return -1.

Examples

Example 1:

1
2
3
4

![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1700-1799/1730.Shortest%20Path%20to%20Get%20Food/images/img1.jpg)
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:

1
2
3
4

![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1700-1799/1730.Shortest%20Path%20to%20Get%20Food/images/img2.jpg)
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:

1
2
3
4

![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1700-1799/1730.Shortest%20Path%20to%20Get%20Food/images/img3.jpg)
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:

1
2

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.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • grid[row][col] is '*', 'X', 'O', or '#'.
  • The grid contains exactly one '*'.

Solution

Method 1 – Breadth-First Search (BFS)

Intuition

Use BFS from the start cell to find the shortest path to any food cell. BFS guarantees the shortest path in an unweighted grid.

Approach

  1. Find the start cell (’*’).
  2. Use BFS to explore the grid, marking visited cells.
  3. Return the distance when a food cell (’#’) is reached, or -1 if not found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

from collections import deque
class Solution:
    def getFood(self, grid):
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '*':
                    sx, sy = i, j
        q = deque([(sx, sy, 0)])
        vis = [[False]*n for _ in range(m)]
        vis[sx][sy] = True
        for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]: pass # for linter
        while q:
            x, y, d = q.popleft()
            if grid[x][y] == '#': return d
            for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                nx, ny = x+dx, y+dy
                if 0<=nx<m and 0<=ny<n and not vis[nx][ny] and grid[nx][ny] != 'X':
                    vis[nx][ny] = True
                    q.append((nx, ny, d+1))
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

import java.util.*;
class Solution {
    public int getFood(char[][] grid) {
        int m = grid.length, n = grid[0].length, sx = -1, sy = -1;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == '*') { sx = i; sy = j; }
        Queue<int[]> q = new LinkedList<>();
        boolean[][] vis = new boolean[m][n];
        q.offer(new int[]{sx, sy, 0});
        vis[sx][sy] = true;
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0], y = cur[1], d = cur[2];
            if (grid[x][y] == '#') return d;
            for (int[] dir : dirs) {
                int nx = x+dir[0], ny = y+dir[1];
                if (nx>=0 && nx<m && ny>=0 && ny<n && !vis[nx][ny] && grid[nx][ny]!='X') {
                    vis[nx][ny] = true;
                    q.offer(new int[]{nx, ny, d+1});
                }
            }
        }
        return -1;
    }
}

Complexity

  • ⏰ Time complexity: O(mn) — Each cell is visited at most once.
  • 🧺 Space complexity: O(mn) — For the visited array and queue.