LeetCode Solutions Blog

Shortest Path to Get Food

Number: 550

Difficulty: Medium

Paid? Yes

Problem Description

Given a grid where each cell can be an obstacle ('X'), free space ('O'), your starting point ('*'), or food ('#'), find the shortest path (in steps) from your starting point to any food cell. You can only move in the four cardinal directions (north, east, south, west). Return the number of steps in the shortest path, or -1 if no such path exists.

Key Insights

Use Breadth-First Search (BFS) to explore the grid level by level.
The BFS guarantees that when a food cell ('#') is reached, the current distance is the shortest.
Maintain a visited structure to avoid re-processing the same cell.
Consider boundary and obstacle ('X') conditions while traversing.

Space and Time Complexity

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns since each cell is processed at most once. Space Complexity: O(m * n) in the worst case due to the queue and visited matrix.

Solution

We use Breadth-First Search (BFS) starting from the cell marked with '*'. The BFS uses a queue to explore neighbors in the four allowed directions (up, down, left, right). Each level of BFS represents one step in the path. As soon as a cell containing food ('#') is reached, the current step count is returned. We also maintain a visited matrix to ensure that cells are not revisited, which could otherwise result in cycles or redundant processing. This approach ensures that the first time we encounter food, we have found the shortest possible path.

Code Solutions

from collections import deque

def getFood(grid):
    # number of rows and columns
    rows = len(grid)
    cols = len(grid[0])
    # finding the start position
    start = None
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '*':
                start = (r, c)
                break
        if start is not None:
            break

    # initialize queue for BFS, with (row, col, steps)
    queue = deque([(start[0], start[1], 0)])
    # mark visited cells to avoid reprocessing
    visited = [[False] * cols for _ in range(rows)]
    visited[start[0]][start[1]] = True
    
    # possible moves: up, right, down, left
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    
    # begin BFS
    while queue:
        row, col, steps = queue.popleft()
        # if food is found, return current number of steps
        if grid[row][col] == '#':
            return steps
        # check all adjacent cells
        for dr, dc in directions:
            newRow, newCol = row + dr, col + dc
            # check boundaries, obstacles, and visited status
            if 0 <= newRow < rows and 0 <= newCol < cols and not visited[newRow][newCol] and grid[newRow][newCol] != 'X':
                visited[newRow][newCol] = True
                queue.append((newRow, newCol, steps + 1))
    
    # if no food is reachable return -1
    return -1

# Example usage:
grid = [
  ["X","X","X","X","X","X"],
  ["X","*","O","O","O","X"],
  ["X","O","O","#","O","X"],
  ["X","X","X","X","X","X"]
]
print(getFood(grid))  # Expected output: 3