Shortest Path to Get Food

medium graph bfs grid

Problem

You are starving and want to eat food as quickly as possible. You are given an m x n character matrix grid where each cell is one of: '*' your location, '#' a food cell, 'O' a free space you can travel through, and 'X' an obstacle you cannot pass. You can move up, down, left, or right to an adjacent free cell.

Return the length of the shortest path for you to reach any food cell. If there is no path for you to reach food, return -1. Because every move costs the same, an ordinary breadth-first search from '*' finds the closest '#' in the fewest steps.

Input

X X X X X
X * O X X
X O X # X
X O O O O
X O X X O

Output5

Shortest route: (1,1)→(2,1)→(3,1)→(3,2)→(3,3)→(2,3), reaching the food in 5 moves.

grid (rows by ';', cells by space; * start, # food, O free, X wall)

from collections import deque

def get_food(grid):
    rows, cols = len(grid), len(grid[0])
    start = None
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '*':
                start = (r, c)
    q = deque([(start[0], start[1], 0)])
    seen = {start}
    while q:
        r, c, d = q.popleft()
        if grid[r][c] == '#':
            return d
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != 'X' and (nr, nc) not in seen:
                seen.add((nr, nc))
                q.append((nr, nc, d + 1))
    return -1

function getFood(grid) {
  const rows = grid.length, cols = grid[0].length;
  let start = null;
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (grid[r][c] === '*') start = [r, c];
  const q = [[start[0], start[1], 0]];
  const seen = new Set([start[0] + ',' + start[1]]);
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  for (let h = 0; h < q.length; h++) {
    const [r, c, d] = q[h];
    if (grid[r][c] === '#') return d;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
      if (grid[nr][nc] === 'X' || seen.has(nr + ',' + nc)) continue;
      seen.add(nr + ',' + nc);
      q.push([nr, nc, d + 1]);
    }
  }
  return -1;
}

class Solution {
    public int getFood(char[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        int[] start = null;
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++)
                if (grid[r][c] == '*') start = new int[]{r, c};
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{start[0], start[1], 0});
        boolean[][] seen = new boolean[rows][cols];
        seen[start[0]][start[1]] = true;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int r = cur[0], c = cur[1], d = cur[2];
            if (grid[r][c] == '#') return d;
            for (int[] dir : dirs) {
                int nr = r + dir[0], nc = c + dir[1];
                if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
                if (grid[nr][nc] == 'X' || seen[nr][nc]) continue;
                seen[nr][nc] = true;
                q.offer(new int[]{nr, nc, d + 1});
            }
        }
        return -1;
    }
}

class Solution {
public:
    int getFood(vector<vector<char>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        int sr = 0, sc = 0;
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++)
                if (grid[r][c] == '*') { sr = r; sc = c; }
        queue<array<int, 3>> q;
        q.push({sr, sc, 0});
        vector<vector<bool>> seen(rows, vector<bool>(cols, false));
        seen[sr][sc] = true;
        int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!q.empty()) {
            auto [r, c, d] = q.front(); q.pop();
            if (grid[r][c] == '#') return d;
            for (auto& dir : dirs) {
                int nr = r + dir[0], nc = c + dir[1];
                if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
                if (grid[nr][nc] == 'X' || seen[nr][nc]) continue;
                seen[nr][nc] = true;
                q.push({nr, nc, d + 1});
            }
        }
        return -1;
    }
};

Explanation

Every move costs exactly one step, so this is an unweighted shortest-path problem — the perfect job for breadth-first search. BFS explores the grid in rings: first all cells one step away from the start, then all cells two steps away, and so on.

We start by finding the '*' cell and pushing it into a queue with distance 0. We also remember which cells we have already queued so we never process one twice.

We pop cells in first-in-first-out order. The moment we pop a cell that holds food ('#'), its recorded distance is guaranteed to be the smallest possible, because BFS always reaches nearer cells before farther ones — so we return it immediately.

From each popped cell we look at the four neighbours. Any neighbour that is inside the grid, is not a wall ('X'), and has not been seen yet gets added to the queue with distance d + 1. If the queue empties without ever finding food, no path exists and we return -1.

Worked example: starting at (1,1), the search fans out down the left column and across the bottom, reaching the food at (2,3) after 5 layers, so the answer is 5.

Time: O(R · C) Space: O(R · C)