LeetCode 1730 - Shortest Path to Get Food

The problem asks us to find the shortest path from a starting location to any food cell in a 2D grid. The grid consists of four types of cells: '' indicating your starting position, '' representing food, 'O' as free space you can move through, and 'X' as obstacles you cannot…

leetcodemediumarraybreadth-first-searchmatrix

LeetCode Problem 1730

Difficulty: 🟡 Medium
Topics: Array, Breadth-First Search, Matrix

Solution

Problem Understanding

The problem asks us to find the shortest path from a starting location to any food cell in a 2D grid. The grid consists of four types of cells: '*' indicating your starting position, '#' representing food, 'O' as free space you can move through, and 'X' as obstacles you cannot traverse. The output should be the minimum number of steps required to reach any food cell. If there is no path to food, the output should be -1.

The input is a 2D matrix of size m x n, where 1 <= m, n <= 200, so we can have up to 40,000 cells. The grid guarantees exactly one starting location '*', but there may be multiple food cells '#' and obstacles 'X'. Movement is allowed in the four cardinal directions: north, east, south, and west. Diagonal moves are not allowed. The constraints imply that a brute-force solution exploring every possible path recursively may not be efficient due to the potential large grid size, so a more structured search is necessary.

Important edge cases include: the starting cell being immediately adjacent to a food cell, the food being completely surrounded by obstacles, or having multiple food cells at different distances where we must find the minimum.

Approaches

A brute-force approach would involve recursively exploring every possible path from the start to any food cell while keeping track of the distance traveled. This guarantees correctness because it eventually examines all paths, but it is inefficient, as it may revisit the same cell multiple times and could take exponential time for large grids.

The optimal approach leverages Breadth-First Search (BFS). BFS is ideal for this problem because it explores all nodes level by level, ensuring that the first food cell we encounter is at the shortest distance from the start. BFS uses a queue to maintain the frontier of exploration and a visited set or in-place marking to avoid revisiting cells. Since the grid is relatively large, BFS guarantees efficiency by stopping as soon as the first food cell is found.

Approach Time Complexity Space Complexity Notes
Brute Force O(4^(m*n)) O(m*n) Recursively explores all paths, highly inefficient for large grids
Optimal O(m*n) O(m*n) BFS ensures shortest path, each cell visited at most once

Algorithm Walkthrough

  1. Scan the entire grid to locate the starting position '*'. Record its coordinates as (start_row, start_col).
  2. Initialize a queue for BFS and enqueue the starting cell along with the initial distance 0.
  3. Optionally, mark the starting cell as visited by replacing '*' with 'X' or maintaining a separate visited matrix.
  4. Define the four possible movement directions: north, south, east, and west.
  5. While the queue is not empty, dequeue a cell (row, col, distance).
  6. Check if the current cell is a food cell '#'. If it is, immediately return the current distance.
  7. Otherwise, explore all four neighboring cells. For each neighbor, ensure it is within bounds and is either free space 'O' or food '#'.
  8. Mark each valid neighbor as visited and enqueue it with distance + 1.
  9. If the queue becomes empty without finding any food cell, return -1 to indicate that no path exists.

Why it works: BFS guarantees that cells are explored in increasing order of distance from the starting point. Therefore, the first time a food cell is encountered, we are guaranteed that the distance recorded is the minimum possible. Visiting each cell at most once prevents cycles and ensures efficiency.

Python Solution

from collections import deque
from typing import List

class Solution:
    def getFood(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        # Find the starting position
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '*':
                    start = (i, j)
                    break

        queue = deque([(start[0], start[1], 0)])  # (row, col, distance)
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        grid[start[0]][start[1]] = 'X'  # mark start as visited

        while queue:
            r, c, dist = queue.popleft()
            if grid[r][c] == '#':
                return dist
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and (grid[nr][nc] == 'O' or grid[nr][nc] == '#'):
                    queue.append((nr, nc, dist + 1))
                    grid[nr][nc] = 'X'  # mark as visited
        return -1

The Python implementation first finds the start cell. The BFS queue stores the current position along with the distance traveled. For each cell dequeued, we immediately check if it is food. If not, we enqueue all valid neighbors. Marking cells as 'X' ensures we do not revisit them. This guarantees the shortest path is found efficiently.

Go Solution

package main

func getFood(grid [][]byte) int {
    m, n := len(grid), len(grid[0])
    var startRow, startCol int
    found := false
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == '*' {
                startRow, startCol = i, j
                found = true
                break
            }
        }
        if found {
            break
        }
    }

    type cell struct{ r, c, dist int }
    queue := []cell{{startRow, startCol, 0}}
    directions := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    grid[startRow][startCol] = 'X'

    for len(queue) > 0 {
        curr := queue[0]
        queue = queue[1:]
        r, c, dist := curr.r, curr.c, curr.dist
        if grid[r][c] == '#' {
            return dist
        }
        for _, d := range directions {
            nr, nc := r+d[0], c+d[1]
            if nr >= 0 && nr < m && nc >= 0 && nc < n && (grid[nr][nc] == 'O' || grid[nr][nc] == '#') {
                queue = append(queue, cell{nr, nc, dist + 1})
                grid[nr][nc] = 'X'
            }
        }
    }
    return -1
}

In Go, we define a struct cell to store row, column, and distance. The BFS logic mirrors Python. Unlike Python, slices in Go require appending for the queue, but the same level-order traversal logic applies. Marking cells as visited avoids revisits.

Worked Examples

Example 1:

Grid:
X X X X X X
X * O O O X
X O O # O X
X X X X X X
  1. Start at (1,1), enqueue (1,1,0).
  2. Dequeue (1,1,0) and explore neighbors: (1,2,1) and (2,1,1) are valid.
  3. Dequeue (1,2,1). Neighbors: (1,3,2) is valid.
  4. Dequeue (2,1,1). Neighbors: (2,2,2) is valid.
  5. Dequeue (1,3,2). Neighbors: (2,3,3) is food.
  6. Return 3.

Other examples follow similarly, exploring level by level until the first food cell is reached.

Complexity Analysis

Measure Complexity Explanation
Time O(m*n) Each cell is visited at most once in BFS
Space O(m*n) Queue may hold all cells in the worst case

BFS ensures linear time relative to the number of cells. Marking visited cells prevents revisiting and ensures the queue does not grow beyond O(m*n).

Test Cases

# Example 1
assert Solution().getFood([["X","X","X","X","X","X"],["X","*","O","O","O","X"],["X","O","O","#","O","X"],["X","X","X","X","X","X"]]) == 3

# Example 2
assert Solution().getFood([["X","X","X","X","X"],["X","*","X","O","X"],["X","O","X","#","X"],["X","X","X","X","X"]]) == -1

# Example 3
assert Solution().getFood([["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