Shortest Path to Get Food in Matrix

Last Updated : 18 Apr, 2024

Given a matrix grid[][], where '*' represents your location, '#' represents food cells, 'O' represents free space, 'X' represents obstacles. The task is to find the shortest path from your location to any food cell in a given matrix grid, Return the length of the shortest path to reach any food cell, or -1 if no path exists.

Example:

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: only 3 steps needed o 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: Not possible to reach the food.

Approach:

The idea is to use multi-source Breadth-First Search (BFS) algorithm. Starts the BFS from the given location and explores the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.

This property of BFS is useful in this problem because it guarantees that we explore all cells at a given distance before moving on to the cells at the next distance. Therefore, the first time we reach a food cell, we can be sure that we have found the shortest path.

Steps-by-step approach:

Initialize a queue (Q) to keep track of cells to visit.
Map grid values ('*', '#', 'O') to integers (1, 2, 3) for better handling.
Find the starting points marked by '*' and add it to the queue.
Perform a Breadth-First Search (BFS) traversal of the grid using the queue.
For each cell popped from the queue:
- If it's a food cell ('#'), update the shortest path length and exit the BFS loop.
- If it's an empty space ('O'), mark it as visited and continue exploring neighboring cells.
- Use a priority queue to ensure food cells are explored first.
At the end of BFS, return the length of the shortest path to reach any food cell. If no path exists, return -1.

Below are the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std; // Function to find the shortest path from your location to // any food cell int findShortestPathToFood(vector<vector<char> >& grid) {  // Initialize a queue to keep track of cells to visit  queue<vector<int> > Q; // <value, distance, x, y>  /*  we mapped grid value to integer:  '*': 1  '#': 2  'O': 3  */  // Define the four possible directions to move in the  // grid  vector<vector<int> > directions  = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };  // Get the size of the grid  int numRows = grid.size(), numCols = grid[0].size();  // Find your location in the grid and add it to the  // queue  for (int row = 0; row < numRows; row++) {  for (int col = 0; col < numCols; col++) {  if (grid[row][col] == '*') {  Q.push({ 1, 0, row, col });  }  }  }  // Initialize the result to -1 (no path found)  int shortestPathLength = -1;  // Create a visited matrix to keep track of visited  // cells  vector<vector<int> > visited(numRows,  vector<int>(numCols));  // Start BFS  while (!Q.empty()) {  auto currentCell = Q.front();  Q.pop();  // If we have reached a food cell, update the  // shortest path length and break  if (currentCell[0] == 2) {  shortestPathLength = currentCell[1];  break;  }  // Visit all adjacent cells  for (int i = 0; i < 4; i++) {  int newRow = directions[i][0] + currentCell[2];  int newCol = directions[i][1] + currentCell[3];  // If the new cell is within the grid, not an  // obstacle, and not visited  if (newRow >= 0 && newRow < numRows  && newCol >= 0 && newCol < numCols  && (grid[newRow][newCol] == 'O'  || grid[newRow][newCol] == '#')  && visited[newRow][newCol] == 0) {  // Mark the new cell as visited  visited[newRow][newCol] = 1;  // If the new cell is a food cell, add it to  // the queue with a priority of 2  if (grid[newRow][newCol] == '#') {  Q.push({ 2, currentCell[1] + 1, newRow,  newCol });  }  // If the new cell is a free space, add it  // to the queue with a priority of 3  else {  Q.push({ 3, currentCell[1] + 1, newRow,  newCol });  }  }  }  }  // Return the length of the shortest path to reach any  // food cell, or -1 if no path exists  return shortestPathLength; } int main() {  vector<vector<char> > grid  = { { 'X', 'X', 'X', 'X', 'X', 'X' },  { 'X', '*', 'O', 'O', 'O', 'X' },  { 'X', 'O', 'O', '#', 'O', 'X' },  { 'X', 'X', 'X', 'X', 'X', 'X' } };  cout << findShortestPathToFood(grid);  return 0; }

Java

import java.util.LinkedList; import java.util.Queue; public class GFG {  // Function to find the shortest path from your location to  // any food cell  public static int findShortestPathToFood(char[][] grid) {  // Initialize a queue to keep track of cells to visit  Queue<int[]> queue = new LinkedList<>(); // <value, distance, x, y>  /*  we mapped grid value to integer:  '*': 1  '#': 2  'O': 3  */  // Define the four possible directions to move in the  // grid  int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};  // Get the size of the grid  int numRows = grid.length;  int numCols = grid[0].length;  // Find your location in the grid and add it to the  // queue  for (int row = 0; row < numRows; row++) {  for (int col = 0; col < numCols; col++) {  if (grid[row][col] == '*') {  queue.add(new int[]{1, 0, row, col});  }  }  }  // Initialize the result to -1 (no path found)  int shortestPathLength = -1;  // Create a visited matrix to keep track of visited  // cells  boolean[][] visited = new boolean[numRows][numCols];  // Start BFS  while (!queue.isEmpty()) {  int[] currentCell = queue.poll();  // If we have reached a food cell, update the  // shortest path length and break  if (currentCell[0] == 2) {  shortestPathLength = currentCell[1];  break;  }  // Visit all adjacent cells  for (int[] direction : directions) {  int newRow = direction[0] + currentCell[2];  int newCol = direction[1] + currentCell[3];  // If the new cell is within the grid, not an  // obstacle, and not visited  if (newRow >= 0 && newRow < numRows  && newCol >= 0 && newCol < numCols  && (grid[newRow][newCol] == 'O'  || grid[newRow][newCol] == '#')  && !visited[newRow][newCol]) {  // Mark the new cell as visited  visited[newRow][newCol] = true;  // If the new cell is a food cell, add it to  // the queue with a priority of 2  if (grid[newRow][newCol] == '#') {  queue.add(new int[]{2, currentCell[1] + 1, newRow, newCol});  }  // If the new cell is a free space, add it  // to the queue with a priority of 3  else {  queue.add(new int[]{3, currentCell[1] + 1, newRow, newCol});  }  }  }  }  // Return the length of the shortest path to reach any  // food cell, or -1 if no path exists  return shortestPathLength;  }  public static void main(String[] args) {  char[][] grid = {  {'X', 'X', 'X', 'X', 'X', 'X'},  {'X', '*', 'O', 'O', 'O', 'X'},  {'X', 'O', 'O', '#', 'O', 'X'},  {'X', 'X', 'X', 'X', 'X', 'X'}  };  System.out.println(findShortestPathToFood(grid));  } }

Python3

from collections import deque # Function to find the shortest path from your location to any food cell def findShortestPathToFood(grid): # Define the four possible directions to move in the grid directions = [(1, 0), (-1, 0), (0, 1), (0, -1)] # Get the size of the grid numRows, numCols = len(grid), len(grid[0]) # Initialize a queue to keep track of cells to visit Q = deque() # (value, distance, x, y) # Find your location in the grid and add it to the queue for row in range(numRows): for col in range(numCols): if grid[row][col] == '*': Q.append((1, 0, row, col)) # Initialize the result to -1 (no path found) shortestPathLength = -1 # Create a visited matrix to keep track of visited cells visited = [[0] * numCols for _ in range(numRows)] # Start BFS while Q: currentCell = Q.popleft() # If we have reached a food cell, update the shortest path length and break if currentCell[0] == 2: shortestPathLength = currentCell[1] break # Visit all adjacent cells for direction in directions: newRow, newCol = direction[0] + currentCell[2], direction[1] + currentCell[3] # If the new cell is within the grid, not an obstacle, and not visited if 0 <= newRow < numRows and 0 <= newCol < numCols and (grid[newRow][newCol] == 'O' or grid[newRow][newCol] == '#') and not visited[newRow][newCol]: # Mark the new cell as visited visited[newRow][newCol] = 1 # If the new cell is a food cell, add it to the queue with a priority of 2 if grid[newRow][newCol] == '#': Q.append((2, currentCell[1] + 1, newRow, newCol)) # If the new cell is a free space, add it to the queue with a priority of 3 else: Q.append((3, currentCell[1] + 1, newRow, newCol)) # Return the length of the shortest path to reach any food cell, or -1 if no path exists return shortestPathLength # Driver code if __name__ == "__main__": grid = [ ['X', 'X', 'X', 'X', 'X', 'X'], ['X', '*', 'O', 'O', 'O', 'X'], ['X', 'O', 'O', '#', 'O', 'X'], ['X', 'X', 'X', 'X', 'X', 'X'] ] print(findShortestPathToFood(grid))

JavaScript

// Function to find the shortest path from your location to any food cell function findShortestPathToFood(grid) {  // Initialize a queue to keep track of cells to visit  const queue = []; // [value, distance, x, y]  /*  We mapped grid value to integer:  '*': 1  '#': 2  'O': 3  */  // Define the four possible directions to move in the grid  const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];  // Get the size of the grid  const numRows = grid.length;  const numCols = grid[0].length;  // Find your location in the grid and add it to the queue  for (let row = 0; row < numRows; row++) {  for (let col = 0; col < numCols; col++) {  if (grid[row][col] === '*') {  queue.push([1, 0, row, col]);  }  }  }  // Initialize the result to -1 (no path found)  let shortestPathLength = -1;  // Create a visited matrix to keep track of visited cells  const visited = new Array(numRows).fill(null).map(() => new Array(numCols).fill(false));  // Start BFS  while (queue.length) {  const currentCell = queue.shift();  // If we have reached a food cell, update the shortest path length and break  if (currentCell[0] === 2) {  shortestPathLength = currentCell[1];  break;  }  // Visit all adjacent cells  for (const direction of directions) {  const newRow = direction[0] + currentCell[2];  const newCol = direction[1] + currentCell[3];  // If the new cell is within the grid, not an obstacle, and not visited  if (newRow >= 0 && newRow < numRows  && newCol >= 0 && newCol < numCols  && (grid[newRow][newCol] === 'O' || grid[newRow][newCol] === '#')  && !visited[newRow][newCol]) {  // Mark the new cell as visited  visited[newRow][newCol] = true;  // If the new cell is a food cell, add it to the queue with a priority of 2  if (grid[newRow][newCol] === '#') {  queue.push([2, currentCell[1] + 1, newRow, newCol]);  }  // If the new cell is a free space, add it to the queue with a priority of 3  else {  queue.push([3, currentCell[1] + 1, newRow, newCol]);  }  }  }  }  // Return the length of the shortest path to reach any food cell, or -1 if no path exists  return shortestPathLength; } // Driver code const grid = [  ['X', 'X', 'X', 'X', 'X', 'X'],  ['X', '*', 'O', 'O', 'O', 'X'],  ['X', 'O', 'O', '#', 'O', 'X'],  ['X', 'X', 'X', 'X', 'X', 'X'] ]; console.log(findShortestPathToFood(grid));