1730. Shortest Path to Get Food


Problem Description

In this problem, you're placed in a grid that represents a map, where your goal is to find the food as quickly as possible. The map includes your current location, marked with a '*', food cells marked with '#', open spaces marked with 'O', and obstacles marked with 'X'. You can move in the four cardinal directions (north, east, south, west) unless an obstacle blocks the way. Your task is to find the length of the shortest path to any of the food cells. Should there be no way to reach any food cell, you must return -1.

Key points of the problem:

  • The grid is a two-dimensional array made up of characters that represent different types of cells.
  • You can only move to adjacent cells (up, down, left, or right), not diagonally.
  • You can't pass through 'X' cells, as these are obstacles.
  • You need to return the shortest number of steps to reach any food cell, not all food cells.

Intuition

The solution to this problem lies in exploring the grid efficiently to find the shortest path to the nearest food cell. A common approach to solving pathfinding problems is to use a breadth-first search (BFS) algorithm. BFS is ideal here because it explores the nearest neighbors first and gradually goes farther away from the start. This feature guarantees that we find the shortest path to the nearest food source.

Here are the steps of the intuition behind the BFS algorithm used:

  1. Locate the starting point where the character '*' is located.
  2. Start the BFS from the starting point, adding the initial position to the queue.
  3. Explore all neighboring cells in the order of north, east, south, and west.
  4. For every valid neighboring cell:
    • If it's a food cell, return the current step count as we've found the shortest path.
    • If it's a free space, mark it as visited by turning it into an obstacle (to avoid revisiting) and add its position to the queue to explore its neighbors in subsequent steps.
  5. The BFS continues until either a food cell is found, or all reachable cells have been explored.
  6. If no food cell is found and exploration is over, return -1 indicating the food is unreachable.

The main idea of this solution is to perform the BFS until the food is found while keeping track of the number of steps taken, ensuring the shortest path is always sought.

Learn more about Breadth-First Search patterns.

Solution Approach

The reference solution approach simply mentions "BFS," indicating that Breadth-First Search is the chosen method for solving the problem. This is the correct approach because BFS ensures we explore paths emanating from the source in an expanding 'wave', where each 'wave' represents an increment in the number of steps required to reach that point. As soon as we encounter a food cell on a wavefront, we can be sure it’s the closest, because if there were a closer one, we would have encountered it on an earlier wave.

To implement BFS, we commonly use a queue data structure because it naturally processes elements in a first-in-first-out (FIFO) order, which aligns with the BFS pattern of visiting all neighbours of a node before moving on to the next level of nodes. In Python, this is often implemented with a deque (double-ended queue) from the collections module for efficient appending and popping.

Let's explain the given Python code provided:

  1. Initial Setup

    1m, n = len(grid), len(grid[0])
    2i, j = next((i, j) for i in range(m) for j in range(n) if grid[i][j] == '*')
    3q = deque([(i, j)])
    4dirs = (-1, 0, 1, 0, -1)

    We start by determining the grid dimensions. The starting point '*' is found using a generator expression that iterates over each cell of the grid. Once found, the location (i, j) is added to the queue q. We also create a tuple of directions dirs that will help us traverse the grid in north, east, south, and west directions.

  2. BFS Loop

    1ans = 0
    2while q:
    3    ans += 1
    4    for _ in range(len(q)):
    5        i, j = q.popleft()
    6        for a, b in pairwise(dirs):
    7            x, y = i + a, j + b
    8            ...

    A while loop begins the BFS process. The count ans will be incremented with each 'wave' of the BFS to reflect the number of steps taken to reach that point. Using len(q) ensures that only the cells that were in the queue at the start of this depth level are processed, which maintains the separation between BFS levels.

  3. Neighbor Traversal and Checks

    1            ...
    2            if 0 <= x < m and 0 <= y < n:
    3                if grid[x][y] == '#':
    4                    return ans
    5                if grid[x][y] == 'O':
    6                    grid[x][y] = 'X'
    7                    q.append((x, y))

    For each node (i, j) processed at the current BFS level, we look at all the possible neighbours by iterating pairwise through the dirs tuple. If a neighbour (x, y) is within the bounds of the grid and is a food cell, we return ans immediately as we've found the shortest path. If it's a free space, we mark it as visited by setting it to 'X' and add its position to the queue to visit its neighbors at the next level.

  4. Handling No Path

    1return -1

    If the BFS completes without finding a food cell ('#'), which means the queue q becomes empty, we return -1 signifying there's no path available.

This implementation efficiently finds the shortest path using BFS, with modifications to mark visited nodes and return the path length immediately upon reaching a food cell.

Example Walkthrough

Let's assume we have the following small grid that represents the map:

1[
2  ['*', 'O', 'O', 'X'],
3  ['O', 'X', 'O', '#'],
4  ['O', 'O', 'X', 'O']
5]

Here is a step-by-step explanation of the algorithm being applied to this grid:

  1. Initial Setup: We find the starting position where '*' is located at (0, 0). We place this position in our BFS queue. Our dirs tuple will help us move through the grid in the cardinal directions.

  2. BFS Loop: We begin a while loop with the BFS process, starting with ans = 0.

  3. First Wave: On the first wave (first iteration of the while loop), the algorithm checks the neighbours of (0, 0). The open spaces on the east ('O', (0, 1)) and south ('O', (1, 0)) are added to the BFS queue. The obstacle ('X', (0, 3)) and the out-of-bound north direction are ignored. The open spaces are then marked as visited by changing them to 'X'.

  4. Increment Step Count: ans is incremented to 1.

  5. Second Wave: On the second wave, the algorithm checks for neighbours of (0, 1) and (1, 0) from the queue. For (0, 1), we check '(1, 1)', '(0, 2)', '(0, 1)' and '(2, 1)'. The only valid movement here is to '(0, 2)' which is an open space. For (1, 0), we can only move to '(2, 0)' since the east is blocked and the south and west cells are out of bounds or visited, respectively. We mark the newly found open spaces as visited.

  6. Increment Step Count: ans is incremented to 2.

  7. Third Wave: The algorithm now checks the neighbours of (0, 2) and (2, 0). From (0, 2), we can only move south to (1, 2). From (2, 0), we can move east to (2, 1) and south to (3, 0), but (3, 0) is out of bounds, so only (2, 1) is considered. These cells are added to the queue and marked as visited.

  8. Increment Step Count: ans is incremented to 3.

  9. Fourth Wave: The algorithm checks neighbour (1, 2). Here, we find the food cell marked with '#' at (1, 3) which is east of our current position. Upon finding the food cell, the BFS algorithm terminates.

  10. Return Shortest Path: Since the food cell is found on the fourth wave, the shortest path length 3 is returned.

Python Solution

1from collections import deque
2
3class Solution:
4    def getFood(self, grid: List[List[str]]) -> int:
5        # Find the size of the grid.
6        rows, cols = len(grid), len(grid[0])
7      
8        # Find the starting position (where the person is located, marked with '*').
9        start_row, start_col = next((row, col) for row in range(rows) for col in range(cols) if grid[row][col] == '*')
10      
11        # Initialize a queue for breadth-first search (BFS) with the starting position.
12        queue = deque([(start_row, start_col)])
13      
14        # Define possible directions to move: up, right, down, and left.
15        directions = ((-1, 0), (0, 1), (1, 0), (0, -1))
16      
17        # Steps taken, initially 0 as we start from the person's position.
18        steps = 0
19      
20        while queue:
21            # Increase the steps taken each time we explore a new layer of neighbors.
22            steps += 1
23          
24            # Explore all positions in the current layer.
25            for _ in range(len(queue)):
26                cur_row, cur_col = queue.popleft()
27              
28                # Explore all adjacent positions.
29                for d_row, d_col in directions:
30                    new_row, new_col = cur_row + d_row, cur_col + d_col
31                  
32                    # Check if the new position is within the grid bounds.
33                    if 0 <= new_row < rows and 0 <= new_col < cols:
34                        # Check if we found food at the new position.
35                        if grid[new_row][new_col] == '#':
36                            return steps
37                      
38                        # If the new position is open space, mark as visited and add to queue.
39                        if grid[new_row][new_col] == 'O':
40                            grid[new_row][new_col] = 'X'  # Mark as visited
41                            queue.append((new_row, new_col))
42                          
43        # If we haven't found food and exhausted all positions, return -1.
44        return -1
45

Java Solution

1class Solution {
2    // Directions represent movement as up, right, down, left (4-connected grid directions)
3    private int[] directions = {-1, 0, 1, 0, -1};
4
5    public int getFood(char[][] grid) {
6        int rows = grid.length, cols = grid[0].length;
7        Deque<int[]> queue = new ArrayDeque<>();
8        // Search for the starting point represented by '*' and add it to the queue
9        for (int i = 0; i < rows; ++i) {
10            for (int j = 0; j < cols; ++j) {
11                if (grid[i][j] == '*') {
12                    queue.offer(new int[] {i, j});
13                    break; // Exit the loop once the starting point is found
14                }
15            }
16        }
17
18        // Initialize number of steps taken to reach the food
19        int steps = 0;
20      
21        // Perform BFS (Breadth-First Search) to find the shortest path to the food
22        while (!queue.isEmpty()) {
23            ++steps; // Increment steps at the start of each level of BFS
24            for (int size = queue.size(); size > 0; --size) {
25                // Poll the current position from the queue
26                int[] position = queue.poll();
27              
28                // Explore all possible next positions using the predefined directions
29                for (int k = 0; k < 4; ++k) {
30                    int x = position[0] + directions[k];
31                    int y = position[1] + directions[k + 1];
32                    // Ensure the next position is within the grid boundaries
33                    if (x >= 0 && x < rows && y >= 0 && y < cols) {
34                        // Check if the food ('#') is found at the current position
35                        if (grid[x][y] == '#') {
36                            return steps; // Return the number of steps taken
37                        }
38                        // Mark visited paths as 'X' and add the new cell to the queue if it's open ('O')
39                        if (grid[x][y] == 'O') {
40                            grid[x][y] = 'X';
41                            queue.offer(new int[] {x, y});
42                        }
43                    }
44                }
45            }
46        }
47        // Return -1 if the food cannot be reached
48        return -1;
49    }
50}
51

C++ Solution

1class Solution {
2public:
3    // Since we will be moving in 4 directions, define an array for the movements
4    const static inline vector<int> directions = {-1, 0, 1, 0, -1};
5
6    // Method to get the minimum steps to reach food from start (*) in the grid
7    int getFood(vector<vector<char>>& grid) {
8        int rows = grid.size(), cols = grid[0].size(); // Get the size of the grid
9        queue<pair<int, int>> toVisit; // Queue to manage BFS
10
11        // Find the starting position and add it to the queue
12        for (int row = 0; row < rows; ++row) {
13            for (int col = 0; col < cols; ++col) {
14                if (grid[row][col] == '*') {
15                    toVisit.emplace(row, col);
16                    break; // Start is found, no need to continue
17                }
18            }
19        }
20
21        int steps = 0; // Initialize the step counter
22
23        // Perform BFS until queue is empty
24        while (!toVisit.empty()) {
25            ++steps; // Increase step counter at each level of BFS
26            for (int sz = toVisit.size(); sz > 0; --sz) { // Process all nodes at current level
27                auto [currentRow, currentCol] = toVisit.front();
28                toVisit.pop(); // Remove the current position from the queue
29
30                for (int k = 0; k < 4; ++k) { // Check all 4 directions
31                    int newRow = currentRow + directions[k], newCol = currentCol + directions[k + 1];
32                    if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) { // Check bounds
33                        if (grid[newRow][newCol] == '#') {
34                            return steps; // Food is found, return answer
35                        }
36                        if (grid[newRow][newCol] == 'O') { // Check if open space
37                            grid[newRow][newCol] = 'X'; // Mark as visited
38                            toVisit.emplace(newRow, newCol); // Add new position to visit
39                        }
40                    }
41                }
42            }
43        }
44
45        return -1; // Return -1 if food cannot be reached
46    }
47};
48

Typescript Solution

1/**
2 * Find the shortest path from a starting point (marked with an asterisk *) to a point with food (marked with a hash #).
3 * The function performs a Breadth-First Search (BFS) on the grid.
4 * 
5 * @param {string[][]} grid The grid represented as a 2D array of characters.
6 * @return {number} The minimum number of steps to reach food from the starting point, or -1 if it cannot be reached.
7 */
8function getFood(grid: string[][]): number {
9    const rows = grid.length;  // The number of rows in the grid.
10    const cols = grid[0].length;  // The number of columns in the grid.
11    // Directions array representing the movement in the adjacent cells (up, right, down, left).
12    const directions = [-1, 0, 1, 0, -1];  
13    // The queue used for BFS, storing the coordinates [row, col] of each point.
14    const queue: [number, number][] = [];
15    // Finding the starting point (where the person is located, marked with an asterisk *) and adding it to the queue.
16    for (let row = 0; row < rows; ++row) {
17        for (let col = 0; col < cols; ++col) {
18            if (grid[row][col] === '*') {
19                queue.push([row, col]);
20                // Break out of both loops once the starting point is found.
21                break;
22            }
23        }
24        // If the queue is not empty, the starting point was found and already added.
25        if (queue.length > 0) {
26            break;
27        }
28    }
29    // The number of steps taken (initialized to 0, incremented before processing each level).
30    let steps = 0;
31    // BFS starting from the initial position.
32    while (queue.length > 0) {
33        steps++;
34        // Iterating through all points at the current BFS level.
35        for (let size = queue.length; size > 0; --size) {
36            const [currentRow, currentCol] = queue.shift()!;
37            // Exploring all four directions from the current cell.
38            for (let k = 0; k < 4; ++k) {
39                const nextRow = currentRow + directions[k];
40                const nextCol = currentCol + directions[k + 1];
41                // Check if the next cell is within grid bounds.
42                if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols) {
43                    // If the cell contains food, return the number of steps.
44                    if (grid[nextRow][nextCol] === '#') {
45                        return steps;
46                    }
47                    // If the cell is open, mark it as visited and add to the queue.
48                    if (grid[nextRow][nextCol] === 'O') {
49                        grid[nextRow][nextCol] = 'X'; // Marking the cell as visited to avoid revisiting it.
50                        queue.push([nextRow, nextCol]);
51                    }
52                }
53            }
54        }
55    }
56    // Return -1 if food is not reachable.
57    return -1;
58}
59

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(m * n). This complexity arises because we perform a breadth-first search (BFS) starting from the initial point where the person is located (denoted by *) and exploring all four directions until we find food denoted by # or until all accessible points are visited.

The worst-case scenario is when the person is located at one corner of the grid and food is at the opposite corner, requiring the BFS to visit every O cell in the m * n grid. Since each cell in the grid is pushed to and popped from the queue at most once, and for each cell, the code checks four directions, the time complexity remains linear with respect to the size of the grid.

Space Complexity

The space complexity of the given code is also O(m * n) in the worst case due to the usage of a queue to store the cells during the BFS. In the worst-case scenario, if the grid is filled with 'O', which is explorable, the BFS would have added most or all of the cells into the queue before finding the food or determining that food cannot be reached. Thus, the maximum space used by the queue can be proportional to the total number of cells in the grid.

Note that the space complexity includes the space for the dirs list and the modified input grid where 'O's are replaced with 'X's as exploration progresses. However, these are not significant in comparison to the space taken by the queue and hence don't affect the overall space complexity order.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫