Shortest Path to Get Food - Practice Coding Problems

Shortest Path to Get Food - Problem

You are starving and want to eat food as quickly as possible. Find the shortest path to arrive at any food cell.

You are given an m x n character matrix grid with these cell types:

'*' is your location (exactly one cell)
'#' is a food cell (may be multiple)
'O' is free space you can travel through
'X' is an obstacle you cannot travel through

You can move to any adjacent cell (north, east, south, west) if it's not an obstacle.

Return the length of the shortest path to reach any food cell. If no path exists, return -1.

Input & Output

Example 1 — Basic Path

$ Input: grid = [["*","O","#"],["O","X","O"],["O","O","O"]]

› Output: 2

💡 Note: Shortest path from '*' at (0,0) to '#' at (0,2): right → right = 2 steps

Example 2 — Blocked Direct Path

$ Input: grid = [["*","X","O"],["O","O","#"],["O","O","O"]]

› Output: 4

💡 Note: Direct path blocked by 'X', must go: down → right → right → up = 4 steps

Example 3 — No Path

$ Input: grid = [["*","X"],["X","#"]]

› Output: -1

💡 Note: Starting position completely surrounded by obstacles, no path to food

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 200
grid[i][j] is '*', '#', 'O', or 'X'
The grid contains exactly one '*'.

Visualization

Tap to expand

Understanding the Visualization

Input Grid

Matrix with start '*', food '#', free 'O', obstacles 'X'

BFS Search

Explore level by level to find shortest path

Path Length

Return steps to reach first food found

Key Takeaway

🎯 Key Insight: BFS guarantees shortest path because it explores all cells at distance k before any cell at distance k+1

Asked in

F Facebook 15 a Amazon 12 G Google 8

The key insight is that BFS guarantees the shortest path in unweighted grids because it explores cells level by level. Best approach is BFS starting from '*' position. Time: O(m×n), Space: O(m×n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force DFS	O(4^(m×n))	O(m×n)	Try all possible paths using depth-first search
Breadth-First Search (Optimal)	O(m×n)	O(m×n)	Use BFS to find shortest path guaranteed

Brute Force DFS — Algorithm Steps

Find starting position '*'
For each food cell '#', run DFS to find path length
Return minimum path length found

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Position

Find starting position '*'

Explore Paths

DFS tries all 4 directions recursively

Track Minimum

Keep track of shortest path to any food

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_SIZE 100

int dfs(char grid[][MAX_SIZE], int m, int n, int row, int col, int visited[][MAX_SIZE], int steps) {
    if (row < 0 || row >= m || col < 0 || col >= n) return INT_MAX;
    if (grid[row][col] == 'X' || visited[row][col]) return INT_MAX;
    if (grid[row][col] == '#') return steps;
    
    visited[row][col] = 1;
    int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int minSteps = INT_MAX;
    
    for (int i = 0; i < 4; i++) {
        int newSteps = dfs(grid, m, n, row + directions[i][0], col + directions[i][1], visited, steps + 1);
        if (newSteps != INT_MAX && newSteps < minSteps) {
            minSteps = newSteps;
        }
    }
    
    visited[row][col] = 0;
    return minSteps;
}

int solution(char grid[][MAX_SIZE], int m, int n) {
    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;
    }
    
    int visited[MAX_SIZE][MAX_SIZE] = {0};
    int result = dfs(grid, m, n, startRow, startCol, visited, 0);
    return result == INT_MAX ? -1 : result;
}

int main() {
    // For demo purposes - would need proper JSON parsing
    char grid[MAX_SIZE][MAX_SIZE];
    int m = 3, n = 3;
    
    printf("%d\n", solution(grid, m, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(4^(m×n))

In worst case, explores all possible paths which can be exponential

✓ Linear Growth

Space Complexity

O(m×n)

Recursion stack depth can be up to m×n in worst case

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler