Coding

Shortest Path to Get Food

Asked at

PhonePe

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an m*n grid where each cell can be one of the following:

***** represents your starting position.There is exactly one ***** cell.
# represents a food location.
O represents an empty space, and you can move through these cells.
X represents an obstacle, and you cannot pass through it. You can move up, down, left, or right and you must find the shortest path to reach a food cell (#). If there is no possible path, return -1.

Input: grid = [["X","X","X","X","X","X"],["X","*","O","O","O","X"],["X","O","O","#","O","X"],["X","X","X","X","X","X"]] Output: 3 Explanation: It takes 3 steps to reach the food.

Input: grid = [["X","X","X","X","X"],["X","*","X","O","X"],["X","O","X","#","X"],["X","X","X","X","X"]] Output: -1 Explanation: It is not possible to reach the food.

Input: 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"]]

m == grid.length
n == grid[i].length
1 <= m, n <= 200
grid[row][col] is '', 'X', 'O', or '#'.
The grid contains exactly one ''.

cpp

class Solution {
public:
    int getFood(vector<vector<char>>& grid) {
       //Your Code Goes Here 
    }
};

java

class Solution {
    public int getFood(char[][] grid) {
        //Your Code Goes Here
    }
}

python

class Solution:
    def getFood(self, grid):

javascript

class Solution {
    getFood(grid) {
    
    }
}

csharp

public class Solution
{
    public int GetFood(char[][] grid)
    {

    }
}

func getFood(grid [][]byte) int {
    //your code goes here
}

Stuck? Show a way to structure it+

01Locate the start cell.
02Enqueue it with distance zero and mark visited.
03Expand four valid non-obstacle neighbors.
04Return when a food cell is first reached.
05Return minus one if the queue empties.

Reference answer

Use BFS because every legal move costs one step. Find the single start cell, enqueue it with distance zero, and mark it visited immediately. Pop cells in FIFO order, examining the four cardinal neighbors that are in bounds, not obstacles, and unvisited. When a neighbor is food, return current distance plus one; the first such discovery is shortest because BFS visits cells by nondecreasing distance. Marking on enqueue prevents multiple parents from adding the same cell. If the queue empties, no food is reachable and return minus one. This is O(m times n) time and O(m times n) space for visited state and the queue. If the start could itself be food, handle that before expanding. DFS can find a path but does not guarantee the shortest one without much more work.

Then expect these follow-ups

How would you return the actual path?
Tests: implementation extension
What changes with different movement costs?
Tests: constraint adaptation

Hiring now

PhonePe has 114 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Engineer, Backend (3-5 years)
Pune, Maharashtra, India
Software Engineer , Backend (5-7 years)
Pune, Maharashtra, India
Software Engineer, App-Android
Bengaluru, Karnataka, India

Or practice this question first

Next question