Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Problem listSolution
DescriptionHints 4SolutionVideo 11:23

1730. Shortest Path to Get Food

Medium57.7% acceptance2 companiesPremium elsewhere, free here

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

Asked at 2 companies

BloombergDoorDash

Topics

ArrayBreadth-First SearchMatrix

Hints open one at a time

Hint 1
Run BFS starting from the '*' position.
Hint 2
Keep the current number of the steps as a state in the queue.
Hint 3
The first time you reach a food, return the number of steps as the answer.
Hint 4
In case the queue is empty and you still did not manage to reach a food, return -1.
11:23
Still stuck?Read the written solution, or watch a walkthrough.
Open solution

Similar problems

01 MatrixMediumShortest Path in a Grid with Obstacles EliminationHardAmount of Time for Binary Tree to Be InfectedMedium
Loading editor…
1class Solution:
2 def solve(self):
3 pass
4
Starter codePython 3Spaces: 4
Examples
Input
[["X","X","X","X","X","X"],["X","*","O","O","O","X"],["X","O","O","#","O","X"],["X","X","X","X","X","X"]]
Input
[["X","X","X","X","X"],["X","*","X","O","X"],["X","O","X","#","X"],["X","X","X","X","X"]]
Input
[["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"]]
Input
[["X","X","X","X","X"],["X","*","X","O","X"],["X","O","X","#","X"],["O","O","O","O","O"]]
Your code is saved on this device.Solution