Shortest Path To Get Food - Leetcode Solution

Problem Statement:

The problem "Shortest Path to Get Food" on LeetCode states that you are given a 2D array of size MxN with four types of elements. These elements are '-','X','','O'. You can move in all four directions from any cell with value ''. Given the starting position of the person and the position of the food, your task is to find the minimum number of steps required to reach the food. If it is not possible to reach the food, return -1.

Solution:

To solve this problem, we can use BFS (Breadth-First Search) algorithm. The idea is to maintain a distance array which will store the minimum distance from the starting cell to any cell in the grid. We can use a queue to perform BFS. Initially, we can add the starting cell to the queue. Then, we can perform BFS until we find the food or the queue becomes empty. In each iteration of the loop, we will remove the first element from the queue and explore its neighbors. If we find the food, we can return the distance to it. Otherwise, we will update the distance in the distance array for each neighbor of the current cell, and add the neighbor to the queue if it is a valid move and has not been visited before.

Algorithm:

1. Initialize an empty queue and a distance array of size MxN with all values as -1.
2. Find the starting cell and add it to the queue. Set its distance to 0 in the distance array.
3. While the queue is not empty, do the following: a. Take the first element from the queue and remove it. b. Explore all four neighbors of the current cell: i. Check if the neighbor is a valid move and has not been visited before. ii. If yes, update its distance to the current cell plus 1 in the distance array and add it to the queue. iii. If the neighbor is the food, return its distance from the starting cell.
4. If the food is not found, return -1.

Code:

Here is the code for the shortest path to get food problem in Python:

from typing import List
from collections import deque

def getFood(grid: List[List[str]]) -> int:
    m, n = len(grid), len(grid[0])

    for i in range(m):
        for j in range(n):
            if grid[i][j] == "*":
                start_i, start_j = i, j
                break

    q = deque([(start_i, start_j)])
    dist = [[-1]*n for _ in range(m)]
    dist[start_i][start_j] = 0

    while q:
        i, j = q.popleft()

        for di, dj in [(1,0), (-1,0), (0,1), (0,-1)]:
            ni, nj = i+di, j+dj
            if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] != "X" and dist[ni][nj] == -1:
                if grid[ni][nj] == "O":
                    return dist[i][j] + 1
                dist[ni][nj] = dist[i][j] + 1
                q.append((ni, nj))

    return -1

Complexity Analysis:

Time Complexity: Since we visit each cell of the grid at most once and perform constant time operations for each cell, the time complexity of this solution is O(M*N).

Space Complexity: We use a queue to maintain the cells to be explored and a distance array to store the distances from the starting cell. Both of these data structures have an upper bound of O(MN). Therefore, the space complexity of the solution is O(MN).

Conclusion:

In this problem, we have learned how to find the shortest path to reach food in an MxN grid of obstacles. Given the starting position of the person and the position of the food, we can use BFS algorithm to find the minimum number of steps required to reach the food.

1