Shortest Path To Get Food In Matrix In C++

In this tutorial, we will explore the process of determining the Most Efficient Route to Reach Food in a Matrix using C++. The scenario involves a 2D array named array, where the top left corner is marked by an asterisk (*), indicating the current position. Food locations are represented by the hash symbol '#', empty spaces by 'O', and obstacles by 'X'. Within this grid defining the food cell positions, the objective is to identify the shortest path from the current position to any food cell and provide the count of steps for the shortest route, or -1 if no viable path is available.

The proposed approach involves implementing a Breadth-First Search (BFS) algorithm that will utilize multiple starting points. Within this algorithm, BFS starts at a designated node and first evaluates the neighboring nodes at the current level before moving on to the subsequent level. An essential characteristic of BFS demonstrated in this scenario is its inherent ability to thoroughly navigate through all cells at a given distance before advancing to cells at a greater distance.

Step-by-step approach:

• ✅ First, give in a source (q) to store visit cells.
• ✅ Mapping grid values ('*', '#', 'O') to integers (1, 2, 3) can be helpful when working with them.
• ✅ Enter the starting points '*' at the line into the queue.
• ✅ Next, implement a Breadth-First Search (BFS) using a queue to traverse the grid.
• ✅ For each cell popped from the queue:
• ✅ If it is a cell of food ('#'), change its shortest path length and then quit the BFS cycle.
• ✅ If it's an empty space ("O"), mark it and move on to explore adjacent cells.
• ✅ Apply a priority queue in such a way that food cells are explored in the least time possible.
• ✅ In the last stage, BFS returns the length of the shortest path to any food cell. If a na is in place, return -1.

Example:

Let's consider an example demonstrating how to determine the most efficient route to reach a food source within a Matrix using C++.

#include <bits/stdc++.h>
using namespace std;

//function for finding the shortest path for food in. matrix
int findShortestPathToFood(vector<vector<char> >& gridmatrix)
{
    // the queue initialization
    queue<vector<int> > Que; // 3 directions

    /*
        mapping up the grid values:
        ?*?: 1
        ?#?: 2
        ?O?: 3

    */

    // Defining the directions of the grid
    vector<vector<int> > directionGrid
        = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

    // find the size of the grid
    int numberOfRows = gridmatrix.size(), numberOfCols = gridmatrix[0].size();

    //Find and add the value to the grid
    for (int r= 0; r< numberOfRows; r++) {
        for (int c = 0; c < numberOfCols; c++) {
            if (gridmatrix[r][c] == '*') {
                Que.push({ 1, 0, r, c });
            }
        }
    }

    //If path not found, then add it 
    //to the result as -1
    int shortPathLength = -1;

    // visited array creation
    vector<vector<int> > visitedMatrix(numberOfRows,
                                 vector<int>(numberOfCols));

    // the bfs loop
    while (!Que.empty()) {
        auto currCell = Que.front();
        Que.pop();

        //If the food cell is reached then update the value
        if (currCell[0] == 2) {
            shortPathLength = currCell[1];
            break;
        }

        // the adjacent cells
        for (int i = 0; i < 4; i++) {
            int nRow = directionGrid[i][0] + currCell[2];
            int nCol = directionGrid[i][1] + currCell[3];

            //If the not visited
            if (nRow >= 0 && nRow < numberOfRows
                && nCol >= 0 && nCol < numberOfCols
                && (gridmatrix[nRow][nCol] == 'O'
                    || gridmatrix[nRow][nCol] == '#')
                && visitedMatrix[nRow][nCol] == 0) {
                // mark if the cell is visited
                visitedMatrix[nRow][nCol] = 1;

                // if teh visited is the food cell then 
                // mark it as prority 2
                if (gridmatrix[nRow][nCol] == '#') {
                    Que.push({ 2, currCell[1] + 1, nRow,
                             nCol });
                }
                // If the visited cell is free, then add 3
                else {
                    Que.push({ 3, currCell[1] + 1, nRow,
                             nCol });
                }
            }
        }
    }

    // return the length
    return shortPathLength;
}

int main()
{

    vector<vector<char> > gridMatrix
        = { { 'X', 'X', 'X', 'X', 'X', 'X' },
            { 'X', '*', 'O', 'O', 'X', 'X' },
            { 'X', 'O', 'O', '#', 'O', 'X' },
            { '*', 'X', 'X', 'X', '*', 'X' } };

    cout << findShortestPathToFood(gridMatrix);

    return 0;
}

Output:

Explanation:

• ✅ This example works with a 2D vector gridmatrix as an input and returns the shortest path length. The Que variable is a queue where information about cells in the grid is stored. Each element in the queue is a vector with four values: type, distance, row, and column. These values are the types of a cell, the distance from the starting cell, and the coordinates of a cell.
• ✅ The directionGrid is a 2D vector that presents the four main directions (up, down, left, right) of the grid.
• ✅ It starts by capturing the number of rows and columns in the matrix. Then, it goes through the whole matrix, to find the beginning cell, which is the dot symbol ('.'). The position where the starting cell is located will be determined by putting a queue labeled "Que" that holds its coordinates, type, and row column values as [1,0, row, column].
• ✅ The main part of the program is a BFS loop that continues until the Que queue is empty. In every step, it picks up a random cell from Que and tests whether it is the food cell (type 2). If not, it updates the shortest path length and breaks out of the loop.
• ✅ Tthe code reads the position of all of the adjacent cells on the right, left, up, and down. Then, if a cell satisfies all four of these conditions: being either an open cell ('O') or a food cell ('#'), being within the griddle borders and not yet visited, it is marked as visited and enqueued into the 'Que' with proper type and distance values.
• ✅ Lastly, the code outputs the minimal path length that indicates the number of steps needed to reach the food cell. Otherwise, the value is -1.