{x}
blog image

Shortest Path to Get Food

1730. Shortest Path to Get Food

Problem Description

Given an m x n character matrix grid representing a map with different cell types:

  • '*': Your starting location (exactly one).
  • '#': A food cell (multiple possible).
  • 'O': Free space.
  • 'X': Obstacle.

Find the shortest path length to reach any food cell from your starting location. You can move north, east, south, or west to adjacent cells. Return -1 if no path exists.

Solution: Breadth-First Search (BFS)

BFS is an ideal algorithm for finding the shortest path in an unweighted graph (like this grid).

Algorithm:

  1. Find Starting Point: Iterate through the grid to find the coordinates of the '*' cell. This is our starting point for BFS.
  2. Initialization: Create a queue q to store the coordinates of cells to visit. Add the starting point to q. Initialize a distance counter ans to 0.
  3. BFS Traversal: While q is not empty:
    • Increment ans (distance increases by 1 with each level).
    • Process all cells at the current distance level (the current queue size):
      • Dequeue a cell (i, j) from q.
      • Explore its four neighbors:
        • If a neighbor is '#', we've found food; return ans.
        • If a neighbor is 'O', it's a valid path. Mark it as visited (e.g., change it to 'X') to prevent cycles and add it to q.
  4. No Path: If the queue becomes empty without finding food, return -1.

Time and Space Complexity

  • Time Complexity: O(m * n), where 'm' and 'n' are the dimensions of the grid. In the worst case, we might visit every cell.
  • Space Complexity: O(m * n) in the worst case, as the queue could hold all cells if the grid is sparsely populated with obstacles. However, in practice, it's usually much less than O(m*n) because many cells are obstacles or are quickly marked as visited.

Code Implementation

The following code implements the BFS solution in several programming languages:

Python3

from collections import deque
 
class Solution:
    def getFood(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        start_row, start_col = -1, -1
        for r in range(m):
            for c in range(n):
                if grid[r][c] == '*':
                    start_row, start_col = r, c
                    break
            if start_row != -1:
                break
        
        q = deque([(start_row, start_col, 0)])  # (row, col, distance)
        visited = set()
        visited.add((start_row, start_col))
 
        while q:
            row, col, dist = q.popleft()
            if grid[row][col] == '#':
                return dist
            
            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                new_row, new_col = row + dr, col + dc
                if 0 <= new_row < m and 0 <= new_col < n and \
                   (new_row, new_col) not in visited and \
                   grid[new_row][new_col] != 'X':
                    q.append((new_row, new_col, dist + 1))
                    visited.add((new_row, new_col))
 
        return -1

Java

import java.util.*;
 
class Solution {
    private static final int[] dr = {0, 0, 1, -1};
    private static final int[] dc = {1, -1, 0, 0};
 
    public int getFood(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int startRow = -1, startCol = -1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '*') {
                    startRow = i;
                    startCol = j;
                    break;
                }
            }
            if (startRow != -1) break;
        }
 
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{startRow, startCol, 0}); // {row, col, distance}
        Set<String> visited = new HashSet<>();
        visited.add(startRow + "," + startCol);
 
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int row = curr[0];
            int col = curr[1];
            int dist = curr[2];
 
            if (grid[row][col] == '#') return dist;
 
            for (int i = 0; i < 4; i++) {
                int newRow = row + dr[i];
                int newCol = col + dc[i];
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n &&
                    !visited.contains(newRow + "," + newCol) &&
                    grid[newRow][newCol] != 'X') {
                    q.offer(new int[]{newRow, newCol, dist + 1});
                    visited.add(newRow + "," + newCol);
                }
            }
        }
        return -1;
    }
}

C++

#include <vector>
#include <queue>
#include <set>
 
using namespace std;
 
class Solution {
public:
    int getFood(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int startRow = -1, startCol = -1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '*') {
                    startRow = i;
                    startCol = j;
                    break;
                }
            }
            if (startRow != -1) break;
        }
 
        queue<tuple<int, int, int>> q; // {row, col, distance}
        q.emplace(startRow, startCol, 0);
        set<pair<int, int>> visited;
        visited.insert({startRow, startCol});
 
        int dr[] = {0, 0, 1, -1};
        int dc[] = {1, -1, 0, 0};
 
        while (!q.empty()) {
            auto [row, col, dist] = q.front();
            q.pop();
 
            if (grid[row][col] == '#') return dist;
 
            for (int i = 0; i < 4; ++i) {
                int newRow = row + dr[i];
                int newCol = col + dc[i];
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n &&
                    visited.find({newRow, newCol}) == visited.end() &&
                    grid[newRow][newCol] != 'X') {
                    q.emplace(newRow, newCol, dist + 1);
                    visited.insert({newRow, newCol});
                }
            }
        }
        return -1;
    }
};

JavaScript

/**
 * @param {character[][]} grid
 * @return {number}
 */
var getFood = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    let startRow = -1, startCol = -1;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === '*') {
                startRow = i;
                startCol = j;
                break;
            }
        }
        if (startRow !== -1) break;
    }
 
    const q = [[startRow, startCol, 0]]; // [row, col, distance]
    const visited = new Set();
    visited.add(`${startRow},${startCol}`);
 
    const dr = [0, 0, 1, -1];
    const dc = [1, -1, 0, 0];
 
    while (q.length > 0) {
        const [row, col, dist] = q.shift();
        if (grid[row][col] === '#') return dist;
 
        for (let i = 0; i < 4; i++) {
            const newRow = row + dr[i];
            const newCol = col + dc[i];
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n &&
                !visited.has(`${newRow},${newCol}`) &&
                grid[newRow][newCol] !== 'X') {
                q.push([newRow, newCol, dist + 1]);
                visited.add(`${newRow},${newCol}`);
            }
        }
    }
    return -1;
};

This detailed explanation and code examples should clarify the solution to the problem. Remember to handle edge cases and potential null values appropriately depending on your chosen language and the input constraints.