#1730 Shortest Path to Get Food

MediumLeetCode PremiumLeetCode page (Premium) ↗free alternative: LeetCode 1926 · Nearest Exit from Entrance in Maze (same one-source grid BFS that stops at the first target) ↗

frequently reported atBloomberg

the problem

In plain words

You're hungry, standing on a char grid. '*' is you (exactly one), '#' is a food cell (there may be several, or none), 'O' is free space and 'X' is an obstacle. Each move goes up, down, left or right onto a non-'X' cell. Return the fewest moves to reach any food cell, or -1 if you can't reach food.

in grid = [[X,X,X,X,X,X],[X,*,O,O,O,X],[X,O,O,#,O,X],[X,X,X,X,X,X]]

out 3

Right, right, down — or down, right, right.

in grid = [[X,X,X,X,X],[X,*,X,O,X],[X,O,X,#,X],[X,X,X,X,X]]

out -1

A column of X splits you from the food.

in grid = [[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,X]]

out 6

The food in row 3 is nearer than the one in row 1.

in grid = [[X,X,X,X,X],[X,*,X,O,X],[X,O,X,#,X],[O,O,O,O,O]]

out 5

Down, down, right, right, up — around the wall through the open bottom row.

1 ≤ m, n ≤ 200
grid[i][j] is '*', 'X', 'O' or '#'
Exactly one '*'

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code right here. Stuck for 20 minutes? Open one hint at a time.

This one is LeetCode Premium. You don't need a subscription: solve it right here. The free alternative linked above is the closest free practice; its label says how close it is.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBFS shortest path (unweighted)

Every move costs the same, so the nearest food is the first food cell a BFS from '*' reaches. One search, stop early — no need to look at every food.

solutions

From brute force to optimal

Run a BFS from each '#' until it finds '*'; keep the shortest.

For each food cell: BFS through non-'X' cells.
When '*' is polled, record the distance.
Answer = the minimum, or -1 if no BFS reached you.

timeO(F · m · n)

F food cells, each BFS may cover the whole grid.

spaceO(m · n)

A distance grid and queue per search.

javajava.util.*

1class Solution {2    /** Run a separate BFS from each food cell towards '*' and keep the shortest. */3    public int getFood(char[][] grid) {4        int best = Integer.MAX_VALUE;5        for (int r = 0; r < grid.length; r++)6            for (int c = 0; c < grid[0].length; c++)7                if (grid[r][c] == '#') {8                    int steps = stepsToYou(grid, r, c);9                    if (steps != -1) best = Math.min(best, steps);10                }11        return best == Integer.MAX_VALUE ? -1 : best;12    }13 14    private int stepsToYou(char[][] grid, int sr, int sc) {15        int rows = grid.length, cols = grid[0].length;16        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};17        int[][] dist = new int[rows][cols];18        for (int[] row : dist) Arrays.fill(row, -1);19        Deque<int[]> queue = new ArrayDeque<>();20        queue.offer(new int[] {sr, sc});21        dist[sr][sc] = 0;22        while (!queue.isEmpty()) {23            int[] cell = queue.poll();24            if (grid[cell[0]][cell[1]] == '*') return dist[cell[0]][cell[1]];25            for (int[] d : dirs) {26                int nr = cell[0] + d[0], nc = cell[1] + d[1];27                if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;28                if (grid[nr][nc] == 'X' || dist[nr][nc] != -1) continue;29                dist[nr][nc] = dist[cell[0]][cell[1]] + 1;30                queue.offer(new int[] {nr, nc});31            }32        }33        return -1;34    }35}

Start BFS at '*', level by level. The first '#' you poll is the nearest food.

Find '*', enqueue it, mark it seen.
For steps = 0, 1, 2…: process exactly the current level.
Polled a '#'? Return steps. Otherwise enqueue unseen non-'X' neighbours.
Queue empty → -1.

timeO(m · n)

Each cell is enqueued at most once and checks 4 neighbours; we may stop early.

spaceO(m · n)

The seen grid and the queue.

javajava.util.*

1class Solution {2    /** One BFS from '*'. Every step costs 1, so the first food cell reached is the nearest. */3    public int getFood(char[][] grid) {4        int rows = grid.length, cols = grid[0].length;5        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};6        boolean[][] seen = new boolean[rows][cols];7        Deque<int[]> queue = new ArrayDeque<>();8        for (int r = 0; r < rows; r++)9            for (int c = 0; c < cols; c++)10                if (grid[r][c] == '*') {11                    queue.offer(new int[] {r, c});12                    seen[r][c] = true;13                }14        for (int steps = 0; !queue.isEmpty(); steps++) {15            for (int size = queue.size(); size > 0; size--) { // one BFS level = one more step16                int[] cell = queue.poll();17                if (grid[cell[0]][cell[1]] == '#') return steps; // first food reached = nearest food18                for (int[] d : dirs) {19                    int nr = cell[0] + d[0], nc = cell[1] + d[1];20                    if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;21                    if (grid[nr][nc] == 'X' || seen[nr][nc]) continue;22                    seen[nr][nc] = true;23                    queue.offer(new int[] {nr, nc});24                }25            }26        }27        return -1; // every reachable cell explored, no food among them28    }29}

in the room

How to say it in the interview

talk track

Say: "Unweighted grid, nearest of several targets → BFS from the single start; the first target reached wins."
Mention the reverse view: a multi-source BFS from all food cells gives the same number — useful if there were many people.
Clarify that food cells can be walked through and that there may be no food at all.

traps

Treating '#' as a wall — food cells are walkable (and the first one ends the search).
Returning when a food cell is enqueued with the wrong level count — keep the step count tied to the level you're processing.
Forgetting the -1 case when every reachable cell has been explored.

what they ask next

Follow-ups

Many people ('*'s), each wants their nearest food?

Flip it: one multi-source BFS from every food cell; each person's answer is the distance written at their cell.

Moving onto some cells costs 2?

Weights break plain BFS. Use Dijkstra (or 0-1 BFS for costs 0/1).

before you submit

Edge cases to test

No food anywhere → -1.
Food right next to you → 1.
The nearest food is walled off but a farther one is reachable.
A 1 × 1 grid that is just '*' → -1.

practise next