Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1730. Shortest Path to Get Food - Leetcode Solution

Problem Description

The "Shortest Path to Get Food" problem involves a 2D grid represented by a list of lists (or a matrix). Each cell in the grid can contain:

  • '*': The starting position (there is exactly one such cell)
  • '#': A food cell (there may be one or more)
  • 'O': An open cell you can walk through
  • 'X': A blocked cell you cannot walk through
The goal is to find the shortest path (in terms of the number of steps) from the starting cell to any food cell, moving only up, down, left, or right. You cannot leave the grid or walk through blocked cells. You may not revisit any cell.

Return the minimum number of steps required to reach any food cell from the starting position. If it is impossible to reach food, return -1.

Thought Process

At first glance, the problem resembles classic pathfinding in a maze. A brute-force approach would be to try all possible paths from the start to every food cell, but this is highly inefficient, especially for larger grids.

Instead, we should look for an efficient way to find the shortest path. Since every move has the same cost and we want the minimal number of steps, this is a perfect scenario for Breadth-First Search (BFS). BFS explores all possible moves level by level, ensuring that the first time we encounter a food cell, it is via the shortest possible path.

Key considerations:

  • We must avoid revisiting cells to prevent cycles and redundant work.
  • We need to keep track of our position and the number of steps taken so far.
  • We must handle edge cases, such as no food being reachable.

Solution Approach

We'll use Breadth-First Search (BFS) to solve this problem efficiently. Here’s how:

  1. Locate the starting cell ('*'): Loop through the grid to find the coordinates of the start.
  2. Initialize BFS structures: Use a queue to manage the cells to explore, starting with the start cell and a step count of 0. Also, use a visited set or matrix to track cells we've already processed.
  3. Process the queue: While the queue is not empty:
    • Pop the front cell and its current step count.
    • If this cell is a food cell ('#'), return the step count.
    • For each of the 4 directions (up, down, left, right), compute the next cell:
      • Check if it's within bounds, not blocked, and not visited.
      • If so, mark as visited and add to the queue with step count + 1.
  4. If the queue empties without finding food: Return -1 as there is no path to any food cell.

We use a queue for BFS because it ensures the first time we reach a cell, it is via the shortest possible path. The visited set prevents infinite loops and redundant work.

Example Walkthrough

Consider the following grid: 

    [['X','X','X','X','X','X'],
     ['X','*','O','O','O','X'],
     ['X','O','O','#','O','X'],
     ['X','X','X','X','X','X']]
  1. We start at (1,1), which is '*'.
  2. BFS explores neighbors: (1,2) and (2,1).
  3. Next, from (1,2): can go to (1,3) and (2,2). From (2,1): can go to (2,2).
  4. Continue expanding: (1,3) to (1,4), (2,2) to (2,3), (2,3) is '#' (food!).
  5. The shortest path is: (1,1) → (1,2) → (1,3) → (2,3), which is 3 steps.

BFS ensures we find this shortest path without exploring longer alternatives.

Time and Space Complexity

Brute-force approach:

  • Could require exploring all possible paths, which is exponential in the number of open cells: O(4n), where n is the number of open cells.
BFS approach:
  • Each cell is visited at most once, so time complexity is O(R × C), where R is the number of rows and C is the number of columns.
  • Space complexity is also O(R × C), mainly for the visited matrix and the queue.

This is optimal for grid-based shortest path problems.

Summary

The "Shortest Path to Get Food" problem is a classic example of grid-based pathfinding. By using Breadth-First Search (BFS), we efficiently find the minimal steps required to reach food, leveraging the fact that BFS always finds the shortest path in an unweighted graph. Avoiding revisiting cells and processing the grid systematically ensures both correctness and efficiency.

Code Implementation

from collections import deque

class Solution:
    def getFood(self, grid):
        rows, cols = len(grid), len(grid[0])
        # Find the start
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '*':
                    start = (r, c)
        queue = deque([(start[0], start[1], 0)])
        visited = set([start])
        directions = [(-1,0), (1,0), (0,-1), (0,1)]
        while queue:
            r, c, steps = queue.popleft()
            if grid[r][c] == '#':
                return steps
            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] != 'X':
                        visited.add((nr, nc))
                        queue.append((nr, nc, steps+1))
        return -1
      
#include <vector>
#include <queue>
#include <utility>
using namespace std;

class Solution {
public:
    int getFood(vector<vector<char>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        int startR, startC;
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (grid[r][c] == '*') {
                    startR = r; startC = c;
                }
            }
        }
        queue<tuple<int,int,int>> q;
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        q.push({startR, startC, 0});
        visited[startR][startC] = true;
        int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};
        while (!q.empty()) {
            auto [r, c, steps] = q.front(); q.pop();
            if (grid[r][c] == '#') return steps;
            for (int d = 0; d < 4; ++d) {
                int nr = r + dr[d], nc = c + dc[d];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                    && !visited[nr][nc] && grid[nr][nc] != 'X') {
                    visited[nr][nc] = true;
                    q.push({nr, nc, steps+1});
                }
            }
        }
        return -1;
    }
};
      
import java.util.*;

class Solution {
    public int getFood(char[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        int startR = -1, startC = -1;
        for (int r = 0; r < rows; ++r)
            for (int c = 0; c < cols; ++c)
                if (grid[r][c] == '*') { startR = r; startC = c; }
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[rows][cols];
        queue.offer(new int[]{startR, startC, 0});
        visited[startR][startC] = true;
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int r = curr[0], c = curr[1], steps = curr[2];
            if (grid[r][c] == '#') return steps;
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                    && !visited[nr][nc] && grid[nr][nc] != 'X') {
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc, steps+1});
                }
            }
        }
        return -1;
    }
}
      
/**
 * @param {character[][]} grid
 * @return {number}
 */
var getFood = function(grid) {
    const rows = grid.length, cols = grid[0].length;
    let startR, startC;
    for (let r = 0; r < rows; ++r)
        for (let c = 0; c < cols; ++c)
            if (grid[r][c] === '*') { startR = r; startC = c; }
    const queue = [[startR, startC, 0]];
    const visited = Array.from({length: rows}, () => Array(cols).fill(false));
    visited[startR][startC] = true;
    const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
    while (queue.length) {
        const [r, c, steps] = queue.shift();
        if (grid[r][c] === '#') return steps;
        for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                && !visited[nr][nc] && grid[nr][nc] !== 'X') {
                visited[nr][nc] = true;
                queue.push([nr, nc, steps+1]);
            }
        }
    }
    return -1;
};